首页 > 代码库 > 【Miller-Rabin随机判素数算法】
【Miller-Rabin随机判素数算法】
实用性介绍：████████████████████████████████
科学性证明：████████████████████████████████
·在运算中尝试使用quick-pow和quick-mul加速。但实际告诉我们，在多次判素数的情况下，使用quick-mul反而会减速，原因可能是原装%运算消耗了大量时间。(复判重复数T取在4以上，不然很危险)
·大米饼目前只能将它作为“黑盒代码”。
1 #include<bits/stdc++.h> 2 #define go(i,a,b) for(int i=a;i<=b;i++) 3 #define T 5 4 #define ll long long 5 using namespace std;int n; 6 ll Mul(ll a,ll b,ll mod){ll R=0;while(b)b&1?b--,R=(R+a)%mod:1,b/=2,a=(a+a)%mod;return R;} 7 ll Pow(ll a,ll b,ll mod){ll R=1;while(b)b&1?R=Mul(R,a,mod):1,b/=2,a=Mul(a,a,mod);return R;} 8 bool witness(ll x,ll a) 9 {10 ll r=x-1,k=0,t;while(!(r%2))r/=2,k++;11 if((t=Pow(a,r,x))==x-1||t==1)return 1;12 while(k--){t=Mul(t,t,x);if(t==x-1)return 1;}return 0;13 }14 bool Miller_Rabin(int x)15 {16 if(x==2)return 1;if(x<2||x%2==0)return 0;go(i,1,T)17 {ll a=1ll*rand()%(x-1-1+1)+1;if(!witness(x,a))return 0;}return 1;18 }19 int main()20 {21 srand(time(NULL));22 while(~scanf("%d",&n))23 {24 if(Miller_Rabin(n))printf("是的是的，是素数。\n");25 else printf("很遗憾,它不是素数(这有什么值得遗憾的呢？)\n");26 }27 return 0;28 }//Paul_Guderian
Try everything to make the world a better place!————Juddy·Hopps
【Miller-Rabin随机判素数算法】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。