数学–米勒罗宾素数检测（Miller-Rabin）（模板+学习）ccsudeer-

参考博客：博客1  博客2

先贴模板

 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define IO ios::sync_with_stdio(false) #define pb push_back #define mk make_pair const int N = 1e5+10; const int mod = 1e9+7;  ll a, b;  const long long S=20;  ll mult_mod(ll a,ll b,ll mod)//快速乘 {  ll res=0;  for(;b;b>>=1){   if(b&1) res=(res+a)%mod;   a=(a+a)%mod;  }  return res; } ll pow_mod(ll a,ll b,ll mod)//快速幂 {  ll res=1;  a%=mod;  for(;b;b>>=1){   if(b&1) res=mult_mod(res,a,mod);   a=mult_mod(a,a,mod);  }  return res; } int check(ll a,ll n,ll x,ll t){     ll ret=pow_mod(a,x,n);//费马小定理 a^(p-1)%p==1     ll last=ret;     for(ll i=1;i<=t;i++){//二次检测定理 如果p是一个素数，则x^2%p==1的解为，则x=1或者x=n-1。         ret=mult_mod(ret,ret,n);         if(ret==1&&last!=1&&last!=n-1) return 1;         last=ret;     }     if(ret!=1) return 1;     return 0; } int Miller_Rabin(ll n){     if(n<2)return 0;     if(n==2)return 1;     if((n&1)==0) return 0;     ll x=n-1;     ll t=0;     while((x&1)==0){x>>=1;t++;}     for(ll i=0;i<S;i++){         ll a=rand()%(n-1)+1;         if(check(a,n,x,t))  return 0;     }     return 1; }  int main(){  for(ll i=100000000000;i<=100000000100;++i){         if(Miller_Rabin(i)) printf("%lld 是素数n",i);         else printf("%lld 不是素数n",i);  } } 

根据概率论学 当一件事发生的概率 低于0.01% 时  这件事就不可能发生，即使在竞赛中倒了 ACM历史以来最大的霉运，出现了判断失误的情况 你就再交一次，总不会次次出现低于0.01%的事件吧，比买彩票中大奖、被闪电劈中的概率低多了。