题意：给你n个数，判读有几个素数
思路：求一个很大的数是不是素数，要用Miller-Rabin算法
#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define int64 long long
int64 qpow(int64 a,int64 b,int64 M){
int64 ans=1;
while(b){
if(b&1)ans*=a,ans%=M;
a*=a;
a%=M;
b>>=1;
}
return ans;
}
bool MillerRabinTest(int64 x,int64 n){
int64 y=n-1;
while(!(y&1))y>>=1;
x=qpow(x,y,n);
while(y<n-1&&x!=1&&x!=n-1)
x=(x*x)%n,y<<=(int64)1;
return x==n-1||y&1==1;
}
bool isprime32(int64 n){
if(n==2||n==7||n==61)return 1;
if(n==1||(n&1)==0)return 0;
return MillerRabinTest(2,n)&&MillerRabinTest(7,n)&&MillerRabinTest(61,n);
}
int main(int argc, char** argv) {
int n,sum,i;
int64 a;
while(scanf("%d",&n)!=EOF){
sum=0;
for(i=0;i<n;i++){
scanf("%lld",&a);
if(isprime32(a))
sum++;
}
printf("%d\n",sum);
}
return 0;
}hdu 2138 How many prime numbers_Miller-Rabin算法模板,布布扣,bubuko.com
hdu 2138 How many prime numbers_Miller-Rabin算法模板
原文：http://blog.csdn.net/neng18/article/details/24365579