前面我们讲了判断素数的方法（复杂度O(√n)），但是它太慢了，所以我们要有一种更快的判断方法。
好像似乎没有在保证正确率的情况下更快的了.......
那就把正确率吃掉好了。
~~很久很久以前，素数突然出现，带来题目带走题解又消失不见~~判断十分危险，复杂度谁最短~~
当然是miller rabin辣！！！
某个神奇的定理：
蒟蒻证明凑合着看233
虽然它的逆定理不一定成立，但是我们可以多找几个a带进去试试吗。如果很多个a都满足的话，那n就很有可能是素数了。选几个a呢？8~10个就够了。a选什么呢？几个小的素数就够了。
题目背景：某ss一直想抽到一只じゅずまるつねつぐ （请自行百度），但是发现他的爆率是1/n（胡诌的，别信）其中n是一个很大很大的数（n>2e9），ss相信如果n是素数，那么ss一定会在有生之年抽到他，请你告诉ss是否能在有生之年抽到他。(じゅずまるつねつぐ爆率感人嘤嘤嘤)
输入格式：
一个数n
输出格式：
如果可以，输出yes
如果不行，输出no
输入样例：
2000000001
输出样例：
no
代码如下：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; long long gg[12]={2,3,5,7,13,29,37,53,59,89,97,1000000007},n; int kuaisumi(long long a,int b,int n){ int ans=1; if(b==0) return a; while(b>0) { if(b&1)ans=ans*a%n; a=a*a%n; b/=2; } return ans; } bool miller_rabin(int a,int b) { int d=n-1,r=0; while(d%2==0) {d/=2;r++; } int x=kuaisumi(a,d,n); if(x==1)return true; for(int i=0;i<=r;i++) { if(x==n-1)return true; x=(long long)x*x%n; } return false; } bool is_prime(int n) { if(n<=1)return false; for(int a=0;a<12;a++) if(n==gg[a])return true; for(int a=0;a<12;a++) if(!miller_rabin(gg[a],n))return false; return true; } int main() { scanf("%lld",&n); if(is_prime(n))cout<<"yes"; else cout<<"no"; }
转载于:https://www.cnblogs.com/lcez56jsy/p/10685939.html
相关资源：数据结构—成绩单生成器