来源：
HDU 2007-11 Programming Contest_WarmUp
题目大意：素数判定。
思路：
事实上暴力判定也可以过，但我还是用了Miller-Rabin算法。
核心思想：利用费马小定理，得到对于质数$p$，我们有$a^{p-1}equiv 1(mod p)$或$a^pequiv a(mod p)$。
反过来，满足条件的不一定是质数，但有很大概率是质数，因此我们只要多随机几个$a$来判定，出错的概率就非常低了。
求幂的运算可以使用Montgomery模幂算法。
注意就算数据在int范围内，中间的运算结果一样会爆int。
一开始还把快速幂中底数和指数的位置打反。
1 #include<ctime> 2 #include<cstdio> 3 #include<cctype> 4 #include<cstdlib> 5 #define int long long 6 inline int getint() { 7 char ch; 8 while(!isdigit(ch=getchar())); 9 int x=ch^'0'; 10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 11 return x; 12 } 13 inline int Montgomery(int a,int b,const int p) { 14 int ret=1; 15 while(b) { 16 if(b&1) ret=ret*a%p; 17 a=(long long)a*a%p; 18 b>>=1; 19 } 20 return ret; 21 } 22 inline bool MillerRabin(const int x) { 23 if(x==2) return true; 24 for(int i=0;i<10;i++) { 25 int a=rand()%(x-2)+2; 26 if(Montgomery(a,x-1,x)!=1) return false; 27 } 28 return true; 29 } 30 signed main() { 31 srand(time(NULL)); 32 int n; 33 while(~scanf("%lld",&n)) { 34 int ans=0; 35 while(n--) { 36 if(MillerRabin(getint())) ans++; 37 } 38 printf("%lld ",ans); 39 } 40 return 0; 41 }
暴力代码：
1 #include<cmath> 2 #include<cstdio> 3 #include<cctype> 4 inline int getint() { 5 char ch; 6 while(!isdigit(ch=getchar())); 7 int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9 return x; 10 } 11 inline bool isPrime(const int x) { 12 for(int i=2;i<=floor(sqrt(x));i++) { 13 if(!(x%i)) return false; 14 } 15 return true; 16 } 17 int main() { 18 int n; 19 while(~scanf("%d",&n)) { 20 int ans=0; 21 while(n--) { 22 if(isPrime(getint())) ans++; 23 } 24 printf("%d ",ans); 25 } 26 return 0; 27 }