以下分别介绍三种素数筛法
思路：发现素数一定是出现在6的倍数的周围，即6n ± 1。简单证明，2和3的倍数既可以筛掉大部分的数字，将2的倍数和3的倍数全部筛掉之后，发现仅剩下6n + 1以及6n + 5，即都出现在6的周围
Code：
#include<cmath>
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;j<x;j++)
{
if(i*prime[j]>N) 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中的最小质因数筛掉。即避免了重复筛选。
原文：https://www.cnblogs.com/TanJI-life/p/14812839.html