普通筛法
int get_primes(int n ){ for(int i = 2; i <= n ; i ++ ) { if(!st[i]) //如果是质数 { primes[cnt ++] = i; } for(int j = i * 2 ; j <= n ; j += i) st[j] = true; //不管当前i是合数还是质数，都用来筛掉后面它的倍数 }}
埃式筛法
int get_primes(int n ){ for(int i = 2; i <= n ; i ++ ) { if(!st[i]) //如果是质数 { primes[cnt ++] = i; for(int j = i * 2 ; j <= n ; j += i) st[j] = true; //只用质数i筛掉它的倍数（合数），也可以筛掉所有合数 } }}
线性筛法
int get_primes(int n ){ for(int i = 2 ; i <= n ; i ++ ) { if(!st[i]) primes[cnt ++] = i; for(int j = 0 ; primes[j] <= n / i ; j ++ ) //判断条件解释：我们用primes[j]筛掉合数primes[j] * i，只用筛掉小于n的合数就可以了 { st[primes[j] * i] = true; if(i % primes[j] == 0) break; } }}