miller_rabin质数筛法
RP(Random polynomial)的时间复杂度
板子
/*
判断一个大整数是否为素数，基于 米勒-拉宾素性检验
input : long long 范围内的一个整数
output : true or flase
*/
#include <bits/stdc++.h>
using namespace std;
#define N 10
typedef long long LL;
LL random(LL n) {
return (LL)((double)rand()/RAND_MAX*n+0.5);
}
LL multi(LL a,LL b,LL m) { //计算a*b%m
LL ret=0;
while(b) {
if(b&1) ret=(ret+a)%m;
b>>=1;
a=(a<<1)%m;
}
return ret;
}
LL quick_mod(LL a,LL b,LL m) { //计算a^b%m
LL ans=1;
while(b) {
if(b&1) {
ans=multi(ans,a,m);
b--;
}
b>>=1;
a=multi(a,a,m);
}
return ans;
}
bool miller_rabin(LL n) {
if(n==2) return true;
if(n<2||!(n&1)) return false;
LL m=n-1;
int k=0;
while((m&1)==0) {
k++;
m>>=1;
}
for(int i=0; i<N; i++) {
LL a=rand()%(n - 1)+1;
LL x=quick_mod(a,m,n);
LL y=0;
for(int j=0; j<k; j++) {
y=multi(x,x,n);
if(y==1&&x!=1&&x!=n-1) return false;
x=y;
}
if(y!=1) return false;
}
return true;
}
int main() {
LL n;
int T;
cin>>T;
while(T--) {
cin>>n;
if(miller_rabin(n)) puts("Yes");
else puts("No");
}
return 0;
}