素数筛法
BT狸——Frozen · · 个人记录
素数的常用筛法
\color{white}\colorbox{white}{~~写了这么多水文，终于有篇正经的了~~}
\color{red}\text{注：本文不是为了标新立异，只是一篇普通的整理}
- 超级普通法
只是利用了素数的定义
时间复杂度
bool Prime0(int x)
{
if(x==1) return 0;//排除特殊
if(x==2||x==3) return 1;
for(int i=2,i<=x;i++)
if(x%i==0) return 0;//不是
return 1; //是
}\color{brown}\text{弊端：这个就不用说了吧}
- 标准常用法
针对基础解法只是将单个时间复杂度降为
bool Prime1(int x) //由于时间复杂度太高 ，只判断单个数
{
if(x==1) return 0;
for(int i=2;i<=sqrt(x);i++)
if(x%i==0) return 0;//不是质数
return 1; //是质数
}\color{brown}\text{弊端:同上}
- 爱拉托斯特尼筛法
\color{red}\text{原理：素数的倍数一定不是素数}
时间复杂度为
int prime[mx];
void Prime2() //时间复杂度 O(n*lglgn)
{
for (int i=0;i<mx;i++) prime[i]=1;//初始化，全体为合数
prime[0]=prime[1]=0;//排除特殊
for (int i=2;i<mx;i++)
{
if(!prime[i]) continue;
for (int j=i*2,j<mx;j+=i) prime[j]=0;//将i倍数标记为合数
}
} \color{brown}\text{弊端：一个数会被筛很多次}
- 线性筛法(欧拉筛）
有点复杂
\color{red}\text{原理：一个合数只会被他最小的质数因子筛去一次}
时间复杂度约为
int vis[mx]，prime[mx];
void prime3() //复杂度 O(n)
{
int cnt=0;
vis[1]=1; //排除特殊情况1
for(int i=2;i<=n;i++)
{
if(!vis[i]) prime[cnt++]=i;
for (int j=0;j<cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1; //倍数去除
if(i%prime[j]==0) break; //去重
}
}
} \color{brown}\text{弊端：为了判断一个大数是否是素数必须从从头开始扫描，而且空间代价也受不了，故不能离散的判断}
- 其它
证明：令x≥1，将大于等于5的自然数表示如下：······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······ 则可以得到，不在6的倍数两侧，即不在6x两侧的数为6x+2，6x+3，6x+4，等于2(3x+1)，3(2x+1)，2(3x+2)，包括6x本身，它们一定不是素数
由此我们可以得到：素数要出现只可能出现在6x的相邻两侧。
此时判断质数可以6个为单元快进，即将方法1循环中i++步长加大为6，加快判断速度。循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6，每次判断循环变量k和k+2的情况即可，理论上讲整体速度应该会是方法1的3倍。（从这篇文章转载）
时间复杂度
bool Prime4(int n)
{
if(n==1) return 0;
if(n==2||n==3) return 1; //特判
if(n%6!=1&&n%6!=5) return 0;
for(register int i=5;i*i<=n;i+=6)
if(n%i==0||n%(i+2)==0) return false;
return true;
}\color{brown}\text{弊端：只是一部分取巧，没有根本解决问题}
- miller rabin算法
\color{red}\text{作用：大概率地判断一个数是否为素数}
基础理论
(1) 费马小定理 (2) 二次探测的证明
具体流程
(1) 直接判断偶数和0，1，2
(2)设要测试的数为x，再取一个较小的质数a，设s,t，满足
(3)计算出
(4)根据费马小定理，若最终
(5)多次取不同a测试，提高正确性
\color{red}\text{时间复杂度}
都是玄学
(1) 出错概率为我也不知道为什么）
(2) 可能是过程太复杂，没有找到关于它的时间复杂度的文章
注意
(1) a越多正确率越高 (2) 当a取小于30的所有素数时，int范围的数不会出错 (3) 由于数据量原因，要使用快速乘和快速幂
代码（附测试）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int prime[10]={2,3,5,7,11,13,17,19,23,29};
typedef long long ll;
ll Quick_Multiply(ll a,ll b,ll c) //快速积
{
ll ans=0,res=a;
while(b)
{
if(b&1)
ans=(ans+res)%c;
res=(res+res)%c;
b>>=1;
}
return ans;
}
ll Quick_Power(ll a,ll b,ll c) //快速幂
{
ll ans=1,res=a;
while(b)
{
if(b&1)
ans=Quick_Multiply(ans,res,c);
res=Quick_Multiply(res,res,c);
b>>=1;
}
return ans;
}
bool Miller_Rabin(ll x)
{
ll s=0,t=x-1,k;
if(x==2) return 1;
if(x<2||!(x&1)) return 0; //排除偶数，0，1
while(!(t&1)) //将x分解为(2^s)*t的样子
{
s++;
t>>=1;
}
for(int i=1;i<10&&prime[i]<x;i++) //开始测试
{
int a=prime[i];
ll b=Quick_Power(a,t,x); //计算a^t
for (int j=1;j<=s;++j) //s次平方
{
k=Quick_Multiply(b,b,x); //求b的平方
if(k==1&&b!=1&&b!=x-1) //二次探求判断
return 0;
b=k;
}
if(b!=1) return 0; //费马小定理判断
}
return 1; //多次实验，是素数
}
int main()
{
ll x;
scanf("%lld",&x);
if(Miller_Rabin(x)) printf("Yes");
else printf("No");
return 0;
}注：本算法难点在于两个定理和快速乘和快速幂
参考资料（复制粘贴）
https://blog.csdn.net/ltyqljhwcm/article/details/53045840
https://blog.csdn.net/forever_dreams/article/details/82314237
https://www.luogu.org/problemnew/solution/P3383