Miller-Rabin素数测试算法（快速判素数 ）

本文主要是介绍Miller-Rabin素数测试算法（快速判素数 ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

复杂度  O（k*log3(n)）

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int prime[10]={2,3,5,7,11,13,17,19,23,29};
int Quick_Multiply(int a,int b,int c)  //快速积（和快速幂差不多）
{long long ans=0,res=a;while(b){if(b&1)ans=(ans+res)%c;res=(res+res)%c;b>>=1;}return (int)ans;
}
int Quick_Power(int a,int b,int c)     //快速幂，这里就不赘述了
{int ans=1,res=a;while(b){if(b&1)ans=Quick_Multiply(ans,res,c);res=Quick_Multiply(res,res,c);b>>=1;}return ans;
}
bool Miller_Rabin(int x)     //判断素数
{int i,j,k;int s=0,t=x-1;if(x==2)  return true;   //2是素数if(x<2||!(x&1))  return false;     //如果x是偶数或者是0,1，那它不是素数while(!(t&1))  //将x分解成(2^s)*t的样子{s++;t>>=1;}for(i=0;i<10&&prime[i]<x;++i)      //随便选一个素数进行测试{int a=prime[i];int b=Quick_Power(a,t,x);      //先算出a^tfor(j=1;j<=s;++j)    //然后进行s次平方{k=Quick_Multiply(b,b,x);   //求b的平方if(k==1&&b!=1&&b!=x-1)     //用二次探测判断return false;b=k;}if(b!=1)  return false;   //用费马小定律判断}return true;   //如果进行多次测试都是对的，那么x就很有可能是素数
}
int main()
{int x;scanf("%d",&x);if(Miller_Rabin(x))  printf("Yes");else  printf("No");return 0;
}

 

这篇关于Miller-Rabin素数测试算法（快速判素数 ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---