1 //**************************************************************** 2 // Miller_Rabin 算法进行素数测试 3 //速度快，而且可以判断 <2^63的数 4 //**************************************************************** 5 const int S=20;//随机算法判定次数，S越大，判错概率越小 6  7  8 LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63 9 {10     a%=mod;11     b%=mod;12     LL ans=0;13     while(b)14     {15         if(b&1)16         {17             ans=ans+a;18             if(ans>=mod)19             ans=ans-mod;20         }21         a=a<<1;22         if(a>=mod) a=a-mod;23         b=b>>1;24     }25     return ans;26 }27 28 LL pow_mod(LL a,LL b,LL mod) // a^b%mod29 {30     LL ans=1;31     a=a%mod;32     while(b)33     {34         if(b&1)35         {36             ans=mult_mod(ans,a,mod);37         }38         a=mult_mod(a,a,mod);39         b=b>>1;40     }41     return ans;42 }43 44 //以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数45 //一定是合数返回true,不一定返回false46 47 bool check(LL a,LL n,LL x,LL t)48 {49     LL ret=pow_mod(a,x,n);50     LL last=ret;51     for(int i=1;i<=t;i++)52     {53         ret=mult_mod(ret,ret,n);54         if(ret==1 && last!=1 && last!=n-1) return true;//合数55         last=ret;56     }57     if(ret!=1) return true;58     else return false;59 }60 61 // Miller_Rabin()算法素数判定62 //是素数返回true.(可能是伪素数，但概率极小)63 //合数返回false;64 65 bool Miller_Rabin(long long n)66 {67     if(n<2)return false;68     if(n==2) return true;69     if( (n&1)==0) return false;//偶数70     LL x=n-1;71     LL t=0;72     while( (x&1)==0 ) { x>>=1;t++;}73     for(int i=0;i