米勒拉宾素数测试可以快速测出单个数是否为素数。
首先需要知道定理:
1. 费马小定理: ap-1≡1(mod p) 其中p为质数
于是,当有一个数n,先判断是不是1,2,3以及2,3的倍数(可以删掉大量数据),此时剩下的都是奇数。
令n-1=2rd,取不同的a,对r从0到最大,满足ad≡1(mod n),此处要分情况。
1)d为奇数,若同余1,可能为质数
2)d为偶数,若同余-1,可能为质数
3)循环后不符合上述情况,必为合数
另外,对于取a的值,通常2,7,61就可计算至2^32数量级,若还需更大,则计算2,3,5,7,11.
模板题hdu2138.
#include <cstdio> int t,n,ans; long long qpow(int x,int y,int mod)//快速幂 { long long ans=1,a=x; while(y) { if(y&1) ans=ans*a%mod; a=a*a%mod; y>>=1; } return ans; } bool MR_prime(int a,int n)//米勒拉宾 { int r=0,d=n-1; if(!(n%a)) return false;//倍数必为合数 while(!(d&1))//找到奇数 { d>>=1; r++; } long long k=qpow(a,d,n); if(k==1) return true;//同余1 for(int i=0;i<r;i++,k=k*k%n) if(k==n-1) return true;//同余-1 return false; } bool check_prime(int n) { if(n==2||n==3||n==7||n==61) return true; if(!(n&1)||n%3==0||n==1) return false;//删掉大量已知情况 if(MR_prime(2,n)&&MR_prime(7,n)&&MR_prime(61,n)) return true; return false; } int main() { while(scanf("%d",&t)!=EOF) { ans=0; while(t--) { scanf("%d",&n); if(check_prime(n)) ++ans; } printf("%d\n",ans); } return 0; }
原文:http://www.cnblogs.com/cons/p/5188910.html