Miller-Rabin素数判断

2024-02-05 15:18

文章标签 判断素数 rabin miller

本文主要是介绍Miller-Rabin素数判断，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个算法要过线性筛模板好难啊
改了好几次才卡到单点800ms过了
其实这个算法就是玄学，就是不断地取随机数，一直用什么什么定理去试，然后还说什么出错几率非常小，其实还是会错的呀，所以要我说就是玄学（虽然模板题100000个数都过了吧。。）
一般来说试10次比较保险，其实5次左右就够（尤其是卡时间的时候）
其实学这个算法就是为了学pollard-rho质因数分解，要不然我会来学这么玄学的东西？
你要知道我的RP是-inf的。。。
好了，上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define ll int
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
const int times=5;
inline ll mul(ll a,ll b,ll p){a%=p;b%=p;ll ans=0;while(b){if(b&1){ans=(ans+a)%p;}a=(a+a)%p;b>>=1;}return ans;
}
inline ll ksm(ll a,ll b,ll p){a%=p;ll ans=1;while(b){if(b&1){ans=mul(ans,a,p);}a=mul(a,a,p);b>>=1;}return ans;
}
inline bool miller_rabin(ll n){if(n==2)return true;if(n<2||(!(n&1)))return false;ll m=n-1;ll k=0;while(!(m&1)){m>>=1;k++;}for(int i=1;i<=times;i++){ll a=rand()%(n-1)+1;ll x=ksm(a,m,n);for(int j=1;j<=k;j++){ll y=mul(x,x,n);if(y==1&&x!=1&&x!=n-1)return false;x=y;}if(x!=1)return false;}return true;
}
int n,m;
int main(){n=read();m=read();while(m--){int x=read();if(miller_rabin(x))printf("Yes\n");else printf("No\n");}return 0;
}