以下分别介绍三种素数筛法

素数判定

思路：

发现素数一定是出现在6的倍数的周围，即6n ± 1。简单证明，2和3的倍数既可以筛掉大部分的数字，将2的倍数和3的倍数全部筛掉之后，发现仅剩下6n + 1以及6n + 5，即都出现在6的周围

Code：

#include
using namespace std;
bool isPrime(int n) {
    if (n < 3) return n > 1;

    if (n % 6 != 1 || n % 6 != 5) return false;
    int end = sqrt(n);    
    for (int i = 5; i <= end; i += 6) { 
        if(n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

埃氏筛法

思路：

? 合数总是可以分解为质数的积，只要将要求的范围内已经求出的所有质数的倍数都去掉，剩下的就是质数

Code：

//Code1:const int N=1e6;
bool vis[N];
void Erat_Prime(int n){
    memset(vis,1,sizeof(vis));
    vis[0]=vis[1]=0;    //0和1均不是素数
    for(int i=2;i*i<=n;i++){
        if(vis[i]){
            for(int j=i*i;j<=n;j+=i)
                vis[j]=0;
        }
    } 
}//Code2:
bool vis[maxn];
int prime[maxn],x;
void Erat_prime(int n) //埃氏筛
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=2;j*i<=n;j++)
        {
            vis[i*j]=true;
        }
    }
}

欧拉筛法

思路：

? 在埃氏筛法的基础上将重复筛的情况去掉。

　　合数总是可以分解为多个质数的积，假如合数a = p1 * p2 * pn（p1，p2，pn均为素数，并且p1 < p2 < pn）,那么筛掉a的方法就有p1 * （p2 * pn）， p2 * （p1 * pn）……n种方式，为了使筛掉的方法唯一，我们规定每次都将合数中的最小质因数为一部分，剩下的为另一部分作为倍数，既可以得到唯一一种筛法，跳过了该合数的其他筛选过程。

Code：

const int N=1e5+10;
int vis[N];    //0表示素数，1表示非素数
int prime[N];    //只在这个函数有作用
void Euler_prime()  //欧拉筛法
{
    for(int i=2;i<=N;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=0;jN) break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

接思路：

? 为了实现让合数分解为——最小质因数 * 剩下的形式，我们将内层循环换为从最小的素数遍历到最大的素数，并且新增一条break语句，使得每次都以prime[j] * i的方式筛掉合数，如此就可以使得prime[j]为该合数的最小质因数。证明如下，改内层循环：prime是从最小遍历到最大的，且i使外层循环，总是大于prime的数字，所以prime[j] < i。加break语句：如果i =k * prime[j]，那么i * prime[j + 1] = prime[j] * k * prime[j + 1]显然此时prime[j + 1]不是该合数i * prime[j + 1]中的最小质因数，那么就说明该合数已经(之后)会被prime[j] 或者k中的最小质因数筛掉。即避免了重复筛选。

欧拉筛

欧拉函数：

? 欧拉函数phi(x)代表小于等于x的数中和x互质的数的个数，如15就有14，13，11，8，7，4，2，1共8个，写做phi(15) = 8。欧拉提出了如下公式，其中pn表示x的质因数（每一种只能用一次）。

phi(x) = x * (1 - 1/p1) * (1-1/p2) * (1 - 1 / p3)…..*(1 - 1/pn)

　　不难发现，欧拉函数和素数有着很深的联系，a = p1 * p2 * pn，欧拉函数需要将所有的质因数都处理一遍（放在上面的式子中），如果使用埃氏筛法，则发现重复计算的部分是p1 * （p2 * pn）， p2 * （p1 * pn）……n种形式，n种方式每次取第一个数字可以将a的质因数都取一遍。

　　下面推导线性筛法，如果每次以——最小质因数 * 剩余部分的方式求欧拉函数，不难发现其推导关系：设a = p1 * b(剩余部分)，则a的质因数与b的质因数只差了一个p1，因此可以得到phi(a) = phi(b) / b * (p1 - 1) / p1 * a = phi(b) * (p1 - 1)。注意break语句的修改部分，由于b = p1 * k，所以b是含有质因数p1的，所以关系式变为phi(a) = phi(b) / b * a = phi(b) * p1。

Code：

void Getphi(int maxn) {
	int k = 0;
	//筛素数也筛欧拉
	for (int i = 2; i < maxn; i++) {
        if (!vis[i]) {
            prime[k++] = i;
            phi[i] = i - 1;
		}
        for (int j = 0; j < k; j++) {
        	if (i * prime[j] >= maxn) break;
        	vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) {        
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			} 
			else 
				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
}