一、素数筛的定义
给定一个整数n，求出[1,n]之间的所有质数(素数)，这样的问题为素数筛(素数的筛选问题)。
二、埃氏筛法(Eratosthenes筛法)
埃氏筛法又叫做Eratosthenes筛法，一般叫做埃氏筛。埃氏筛的思想是：
(forall xin Z)的倍数(2x，3x，...)都不是质数。
因此我们可以从2开始有小到大扫描每个数(x)，并把(x)的倍数(2x，3x，4x，...)标记为合数。当这个某个数(y)被扫描到的时候，如果(y)没有被标记为合数，那么(y)就属于质数。
Eratosthenes筛法的复杂度为(O(NloglogN))。效率非常接近线性。
以下为Eratosthenes筛法模板：
inline int Eratosthenes(int n){
for(int i=1;i<=n;i++) is_p[i]=1;
memset(prime,0,sizeof(prime));
is_p[1]=is_p[0]=0;
for(int i=1;i<=n;i++){
if(!is_p[i]) continue;
prime[++tot]=i;//prime[]存储了[1,n]的所有质数
for(int j=i*2;j<=n;j+=i) is_p[j]=0;//j为合数
}
return tot;
}
三、线性筛法
我们知道，一个算法的复杂度组成有一类是因为重复的计算。这就是埃氏筛的问题所在，埃氏筛会重复标记已标记的合数。例如12会被质数2重复标记，同时也会被3标记。如果我们仅能标记一次合数就好了。
线性筛法通过从大到小不断累乘质因子的方法标记合数，即12的标记方式为：(12=6 imes 2=(3 imes2) imes2)。
实现方式为：
1.依次扫描[2,n]的每一个数a
2.若没有被标记为合数，说明a是质数，此时保存起来
3.依次扫描(a imes prime[x]leqslant n)的每一个质数，标记(a imes prime[x])为合数，且保证prime[x]为(a imes prime[x])的最小质因子。
因为每个合数只会被它的最小质因子筛一次，所以线性筛的复杂度为(O(N))。
以下为线性筛法的模板：
int notp[N],prime[N];
inline int get_primes(int n){
int tot=0;
for(int i=2;i<=n;i++){
if(!notp[i]) prime[++tot]=i;
for(int j=1;j<=tot,i*prime[j]<=n;j++){
notp[i*prime[j]]=1;//标记合数，此时prime[j]是合数i*prime[j]的最小素因子
if(i%prime[j]==0) break;
//一个小合数与大质数 可以被 一个大合数与小质数 替代
//3*6=18，同样的，2*9=18。此时我们不如让2*9标记18
}
}
return tot;
}
四、一个性质
- 任何一个合数n必定包含一个不超过(sqrt n)的质因子。
