How many PRime numbers

32 3 4 Sample Output
2 Authorwangye SourceHDU 2007-11 Programming Contest_WarmUp Recommend威士忌   |   We have carefully selected several similar problems for you:  2136 1431 2132 2139 2012 
題解：Miller Rabbin大質數判定
控制一下嘗試的次數，此題容易TLE
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define LL long longusing namespace std;int n;LL quickpow(LL num,LL x,LL p){	LL base=num%p; LL ans=1;	while (x) {		if (x&1) ans=ans*base%p;		x>>=1;		base=base*base%p;	}	return ans; }bool miller_rabbin(LL n){	if (n==2) return true;	if (n<2||!(n&1)) return false;	LL t=0;	LL a,x,y,u=n-1;	while (!(u&1)) t++,u>>=1;	for (int i=0;i<=100;i++) {		a=rand()*rand()%(n-1)+1;		x=quickpow(a,u,n);		for (int j=0;j<t;j++) {			y=x*x%n;			if (y==1&&x!=1&&x!=n-1) return false;			x=y;		}		if (x!=1) return false;	} 	return true;}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	while (scanf("%d",&n)!=EOF){	    int cnt=0;		for (int i=1;i<=n;i++) {			int x; scanf("%d",&x);			cnt+=miller_rabbin((LL)x);		} 		printf("%d/n",cnt);    }}