题目描述
给定一个正整数 n,请你求出 1∼n
中质数的个数。
输入格式
共一行,包含整数 n
。
输出格式
共一行,包含一个整数,表示 1∼n
中质数的个数。
数据范围
1≤n≤106
输入样例:
8
输出样例:
4
样例
blablabla
算法1
(欧拉筛) $O(n)$
import java.util.Iterator;
import java.util.Scanner;
public class Main {
static int N=1000010;
static int cnt=0;
static int[] prime = new int[N];
static boolean[] st = new boolean[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
get_prime(n);
System.out.println(cnt);
}
private static void get_prime(int n) {
for (int i = 2; i <=n; i++) {
if(!st[i]) prime[cnt++]=i;
for (int j = 0; i*prime[j]<=n; j++) {
st[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
}