根据费马小定理，若p为素数，则必有a^(p-1) mod p=1 对和p互质的a成立。
根据二次探测定理：如果p是素数，且0<x<p，则方程x^2 mod p=1的解为1或p-1。
所以若p为素数，则必有a^(p-1) mod p 的平方根为1或-1
分解p-1为d*2^s，其中d为奇数
从i=0逐次计算a^(d*2^(s-i))，相当于“开方”，若得到-1或追查到a^d=1 (mod p)，则p通过测试，否则不通过
时间复杂度O(k*(logn)^3) （其中k为选的a的个数（the more the better?））
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; const int prime[]={,,,,,,,,}; int n; int quick(int a,int b,int mod){
int sum=;
for(;b;b>>=,a=a*a%mod)
if(b&) sum=sum*a%mod;
return sum;
} bool Rabin_Miller(int p,int a){
if(p==) return ;
if((p&)==||p==) return ;
int d=p-;
while((d&)==) d>>=;
int m=quick(a,d,p);
if(m==) return ;
for(;d<p;d<<=,m=m*m%p)
if(m==p-) return ;
return ;
} bool isprime(int x){
for(int i=;i<;i++){
if(x==prime[i]) return ;
if(!Rabin_Miller(x,prime[i])) return ;
}
return ;
} int main(){
scanf("%d",&n);
if(isprime(n)) puts("Yes!");
else puts("No!");
return ;
}