米勒拉宾素数测试可以快速测出单个数是否为素数。
首先需要知道定理：
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