AcWing 868. 筛质数
原题链接
简单
import java.util.*;
public class Main {
static final int N = (int) 1e6 + 10;
static int[] primes = new int[N];
static int cnt = 0;
static boolean[] st = new boolean[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
// j从小到大枚举,所以某个数x一定是被最小质因子筛掉
// 由于每个数只有1个最小质因子,所以每个数只会被筛1次
// 由于质因子只需要枚举到较小的那个即可,所以只需要枚举到n / i
for (int j = 0; primes[j] <= n / i; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
System.out.println(cnt);
}
}