筛法求素数
筛法求素数
前言
素数（质数）：除了1和它本身以外不再有其他因数（能被整除的数）
合数：除了能被1和本身整除外，还能被其他数整除的数
互质：公约数只有1的两个整数
题目：判断1-n的范围内有多少个素数？oj练习
判断一个数是否为素数，一般会想到以下代码
//时间复杂度O(n*sqrt(n))
bool sushu(int n){
if(n<=1) return 0;
for(int i=2;i<=sqrt(n);++i){
if(n%2==0) return 0;
}
return 1;
}当n取很大时，每判断一个数 i（1<=i<=n）是否为素数，都要枚举sqrt(i)次，时间复杂度接近O(n^2)，
提前建立一张素数表，再通过查表的方式来判断素数。而这里打表的算法，就需要用到筛法，把表中不是素数的筛去
这里介绍两种常用的筛法：埃氏筛、欧拉筛（线性筛）
埃氏筛
埃氏筛的思想：素数的倍数都不是素数，如2的倍数（即偶数）都不是素数
用一个prime[n] bool数组来打表，prime[i]=0表示i是素数，prime[i]=1表示i不是素数
一开始都初始化为0，都认为是素数，然后慢慢把不是素数的筛去（prime标为1）
先标记prime[1]=1，因为1不是素数
接着从2开始，把2的所有倍数（合数）都一个个筛去…
//时间复杂度O(nloglogn)
#define ll long long
ll n;
bool prime[1000005]; //一开始都认为是质数（初始化为0），0代表是质数，1代表不是
void ai_shai(){
prime[1]=1; //1不是质数
for(ll i=2;i<=n;++i)
if(prime[i]==0) //如果是质数
for(ll j=i*i;j<=n;j+=i) //从i*i开始筛选 因为2*i~(i-1)*i 之前已被2~(i-1)筛出来了
prime[j]=1; //质数的倍数都不是质数
}上述的从i*i开始筛选可以理解为，比如轮到3的时候，可以从3*3开始筛选，因为3*2已经被2*3筛去了
还有为什么要判断是否为素数后再进行筛选，还是举个例子，4不是素数，4的倍数比如8、16等之前已经被2给筛过了2*4、2*8，就会产生多余步骤
欧拉筛（线性筛）
埃氏筛的时间复杂度为O(nloglogn)，如何更进一步的优化？
仔细观察可发现，上面的埃氏筛也有一些重复计算，有些数会被不同的素数筛多次，比如30=3*10，30=5*6等
所以欧拉筛的思想就是：在埃氏筛的基础上，让每个合数只被其最小的质因数筛一次
这使得欧拉筛的时间复杂度可以达到O(n)的线性复杂度，所以欧拉筛也称线性筛
建立两个数组，一个是bool类型的素数表prime，用来表示prime[i]是不是素数。另一个是int类型用来存储每个素数的数组zyz，每个素数都会成为某个合数的最小质因子
代码如下，注释详细：
bool prime[1000005]; //1代表不是素数，0代表是素数
int zyz[1000005]; //合数最小的质因子，也记录着每一个质数
int cnt=0; //记录质数的个数
void ol_shai(){
prime[1]=1; //1不是质数
for(int i=2;i<=n;++i){
if(prime[i]==0) //如果是质数
zyz[++cnt]=i; //i是一个素数，存入zyz数组中
for(int j=1;j<=cnt&&i*zyz[j]<=n;++j){ //每个素数对应的i倍筛下来
prime[i*zyz[j]]=1; //合数i*zyz[j]的最小质因子是zyz[j]
if(i%zyz[j]==0) break;
//如果zyz[j]还是i的最小质因数，后面的合数i*zyz[j+1]会被zyz[j](最小质因数)筛选
}
}
}其中有关break的语句，这里拿出来再解释一下
如果i%zyz[j]=0，这里设一个数k，k*zyz[j]=i，下一个循环的i*zyz[j+1]可以分解为k*zyz[j]*zyz[j+1]，其中最小质因数为zyz[j]，所以会在zyz[j]中被（k*zyz[j+1]）筛选出来
举个例子，i=9，j=2，zyz[2]=3，9%3=0，如果没有break，那么j=3，zyz[3]=5，9*5=3*3*5=3*15，最小质因数为3，会在i=15的时候，被zyz[2]=3筛出来
这个关键的break保证了，一个合数只被最小质因数筛出，使得O(n)的时间复杂度得以成立