AcWing 868. 筛质数
原题链接
简单
线性筛法,保证了每个合数只会被它的最小质因子筛掉,并且只会被筛一次
由于每个数只有1个最小质因子,所以在线性筛法中,每个数只会被筛1次
import java.util.*;
public class Main {
static final int N = 1000010;
static int[] nums = new int[N];
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;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
System.out.println(cnt);
}
}
补充几点:
1、当i % primes[j] == 0时,不退出循环的话,就会出现重复筛选,why?
由于primes[j]是i的最小质因子,那么primes[j]也应该是primes[j + 1] * i的最小质因子(比如primes[j] == 2, prime[j + 1] == 3, i == 4,用3和4去筛12就不对了)
2、当i % primes[j] != 0时,说明prime[j]小于i的最小质因子,也说明primes[j]为primes[j] * i的最小质因子
3、关于为什么是primes[j] <= n / i。虽然质因子可能大于sqrt(n),但那只是其中一个,另一个质因子一定小于sqrt(n),所以n的最小质因子一定小于sqrt(n)