质数筛

暴力筛
代码:

1 bool check_prime(int n)
2 {
3 　　if(n==1) return 0;
4 　　for(int i=1;i<=n;i++)
5 　　if(n%i==0) return 1;
6 　　return 0;
7 }

六筛法
代码：

 1 bool check_prime(int n)
 2 {
 3     if(n==1) return 0;//1既不是质数也不是合数 
 4     if(n==2||n==3) return 1;//2,3不是6两侧的数但他是质数 
 5     if(n%6!=1&&n%6!=5) return 0;//质数只能是6两侧 
 6     int x=sqrt(n);//筛到根号n 
 7     for(int i=5;i<=x;i++)
 8         if(n/i==0||n/(i+2)==0) return 0;//如果他还有约数 
 9     return 1;//若没有约数 
10 }

引理:算术基本定理——任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积
所以只需要n无法被质数整除n即为质数
由于6两侧的数不是2和3的倍数所以不需要用2和3来筛
也不需要用6n+2,3,4来筛因为这些都是2和3的倍数，如果该数能被筛掉则改该数也能被2和3整除，不符合上述条件

线性筛 （也叫欧拉筛）
代码：

int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;//如果没有没有被筛掉就存入primes 
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}            

引理:算术基本定理——任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积
显然,在所有大于0的自然数中,除了质数就是合数.要求质数,只需要”筛”去所有的合数即可.如何筛去合数
这里就应用到了算术基本定理.关于合数,这里我们需要注意两点:
(1).所有合数都要筛到
(2).不能有重复筛选,否则无法达到在线性时间内的运行了
要做到第一点,根据算术基本定理:n=q*m(q表示最小质数,m=N/q,显然m>=q),对N内的m和q进行枚举
这样我们就保证了能枚举N以内的所有整数,然而我们还不能保证枚举的合数不重复。

重点：先来思考一下为什么会有重复,由于对于任意一个n=m*q,m和q是相对的两个状态,m大了q就变小,m小了q就变大。

重点：设n=m1*q1=m2*q2,q1<=q2<=m2<=m1我们这里需要保证当且仅当在q1是最小质因数时能求解,也就是去除q2和m2的情况.

重点：因为q1与q2互质,且q1<q2,则有m2%q1=0;由于每一个i值都是不同的因此我们认为当前的i值符合m1的条件因此临界条件为

重点：q1=q2，m2=m1，此时q1再增大时就有危险因为此时不符合除去q2和m2的条件

所以关键步骤来了: if(i%peimes[j]==0) break;
当i是primes[j]的倍数时直接跳出循环,设i=primes[j]*t,此时有i*primes[j+1]=primes[j]*t*primes[j+1]
可以看到此时的最小质数时primes[j],为了避免与当m=primes[j+1]*t时有重复,这里可以通过break跳过计算
此外还需注意:要保证m从2开始,因为1*q=1且i%1==0;

原文：https://www.cnblogs.com/HYfeng-yanwu/p/13848283.html