Miller-Rabin质数测试

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long LL;
 8 LL mul_mod(LL a,LL b,LL mod){
 9     LL ret=0;
10     while(b){
11         if(b&1)    ret=ret+a;
12         if(ret>=mod)    ret-=mod;
13         a=a+a;
14         if(a>=mod)    a-=mod;
15         b>>=1;
16     }
17     return ret;
18 }
19 LL pow_mod(LL a,LL b,LL mod){
20     LL ret=1;
21     while(b){
22         if(b&1)ret=mul_mod(ret,a,mod);
23         a=mul_mod(a,a,mod);
24         b>>=1;
25     }
26     return ret;
27 }
28 bool Miller_Rabin(LL n){//判断素数 
29     LL u=n-1,pre,x;
30     int i,j,k=0;
31     if(n==2||n==3||n==5||n==7||n==11)    return true;
32     if(n==1||(!(n%2))||(!(n%3))||(!(n%5))||(!(n%7))||(!(n%11))) return
33             false;//初始化判断素数 
34     for(;!(u&1);k++,u>>=1);//按照要求转换形式 
35     for(i=0;i<5;i++){
36         x=rand()%(n-2)+2;//生成随机数 
37         x=pow_mod(x,u,n);
38         pre=x;
39         for(j=0;j<k;j++){
40             x=mul_mod(x,x,n);
41             if(x==1&&pre!=1&&pre!=(n-1))//二次探测判断 
42                 return false;
43             pre=x;
44         }
45         if(x!=1) return false;//用费马小定理判断 
46     }
47     return true;
48 }
49 int main(){
50     LL n,T;
51     scanf("%lld",&T);
52     while(T--){
53         scanf("%lld",&n);
54         if(Miller_Rabin(n)) puts("Yes");
55         else puts("No");
56     }
57     return 0;
58 }