MillerRabin
点击查看代码
int test[10]={0,2,3,5,7,11,13,17,19,23};
int qpow(int x,int p,int mod){
int ans=1;
while(p){
if(p&1) ans=(ans*x)%mod;
x=(x*x)%mod;
p>>=1;
}
return ans;
}
int MillerRabin(int p){
if(p==1) return 0;
int k=0,t=p-1;
while(!(t&1)) k++,t>>=1;
for(int i=1;i<=8;i++){
if(p==test[i]) return 1;
int now=qpow(test[i],t,p),la=now;
for(int j=1;j<=k;j++){
now=(1ll*la*la)%p;
if(now==1&&la!=1&&la!=p-1) return 0;
la=now;
}
if(now!=1) return 0;
}
return 1;
}