米勒拉宾算法的基本概念如下：

首先判断这个数n的奇偶性

若为偶数仅有2是质数

奇数则进入测试

测试方法：

首先确定几个基底a,范围在[2,n-1]

因为n是奇数,所以n-1必定为偶数

则n-1可以表示为(2^s)*d

s、d分别求出来

设t为a^d模n的数,有如下几个约定：

1.若t=-1或1时则该数n可能为质数

2.若此时t=n-1,则该数可能为质数

3.d*2>n-1时n必为合数

4.若上述皆不满足则让d*2,返回2

多组测试之后就能判断是否为质数,而且错误率相当低！！

 

 

不过想证明米勒拉宾的正确性还是很困难的

需要费马小定理等七七八八的数论

具体的可以百度

我就不给于证明了~

直接上模板：

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define ll long long 6 using namespace std; 7  8 ll add_mod(ll a,ll b,ll mod){    //快乘法 基于快速幂的二分思想  9     ll ans=0;                    //由于考虑到取模数很大 快速幂会溢出 10     while(b){                    //必须使用该方法 11         if(b&1)                    //我这里写的是非递归版 12             ans=(ans+a)%mod;13         a=a*2%mod;14         b>>=1;15     }16     return ans;17 }18 19 ll pow_mod(ll a,ll n,ll mod){            //快速幂 递归版 20     if(n>1){                            21         ll tmp=pow_mod(a,n>>1,mod)%mod;22         tmp=add_mod(tmp,tmp,mod);23         if(n&1) tmp=add_mod(tmp,a,mod);24         return tmp;25     }26     return a;27 }28 29 bool Miller_Rabbin(ll n,ll a){
    //米勒拉宾素数判断函数主体30     ll d=n-1,s=0,i;    31     while(!(d&1)){            // 先把(2^s)*d 算出来 32         d>>=1;33         s++;34     }35     ll t=pow_mod(a,d,n);    //a^d取一次余判断 36     if(t==1 || t==-1)        //一或负一则可以声明这可能是质数 37         return 1;38     for(i=0;i
          
           tab[i] && !Miller_Rabbin(n,tab[i]))54             return 0;55     }56     return 1;57 }58     59 int main(){60     ll n;61     scanf("%lld",&n);62     if(n<2) printf("No");63     else if(n==2) printf("Yes");64     else{65         if(!n%2) printf("No");66         else if(is_prime(n))67             printf("Yes");68         else printf("No");69     }70     return 0;71 }