I. Older Brother

Your older brother is an amateur mathematician with lots of experience. However, his memory is very bad. He recently got interested in linear algebra over finite fields, but he does not remember exactly which finite fields exist. For you, this is an easy question: a finite field of order q exists if and only if q is a prime power, that is, q = p^kp​k​​ holds for some prime number pand some integer k ≥ 1. Furthermore, in that case the field is unique (up to isomorphism).

The conversation with your brother went something like this:

Input

The input consists of one integer q, satisfying 1 ≤ q ≤ 10^910​9​​.

Output

Output “yes” if there exists a finite field of order q. Otherwise, output “no”.

 //2017-10-24

 #include <cstdlib>

 #include <iostream>

 #include <ctime>

 typedef long long LL;

 #define MAXN 10000

 using namespace std;

 LL factor[MAXN];

 int tot;

 const int S=;

 LL muti_mod(LL a,LL b,LL c){    //返回(a*b) mod c,a,b,c<2^63

     a%=c;

     b%=c;

     LL ret=;

     while (b){

         if (b&){

             ret+=a;

             if (ret>=c) ret-=c;

         }

         a<<=;

         if (a>=c) a-=c;

         b>>=;

     }

     return ret;

 }

 LL pow_mod(LL x,LL n,LL mod){  //返回x^n mod c ,非递归版

     if (n==) return x%mod;

     int bit[],k=;

     while (n){

         bit[k++]=n&;

         n>>=;

     }

     LL ret=;

     for (k=k-;k>=;k--){

         ret=muti_mod(ret,ret,mod);

         if (bit[k]==) ret=muti_mod(ret,x,mod);

     }

     return ret;

 }

 bool check(LL a,LL n,LL x,LL t){   //以a为基，n-1=x*2^t，检验n是不是合数

     LL ret=pow_mod(a,x,n),last=ret;

     for (int i=;i<=t;i++){

         ret=muti_mod(ret,ret,n);

         if (ret== && last!= && last!=n-) return ;

         last=ret;

     }

     if (ret!=) return ;

     return ;

 }

 bool Miller_Rabin(LL n){

     LL x=n-,t=;

     while ((x&)==) x>>=,t++;

     bool flag=;

     if (t>= && (x&)==){

         for (int k=;k<S;k++){

             LL a=rand()%(n-)+;

             if (check(a,n,x,t)) {flag=;break;}

             flag=;

         }

     }

     if (!flag || n==) return ;

     return ;

 }

 LL gcd(LL a,LL b){

     if (a==) return ;

     if (a<) return gcd(-a,b);

     while (b){

         LL t=a%b; a=b; b=t;

     }

     return a;

 }

 //找出任意质因数

 LL Pollard_rho(LL x,LL c){

     LL i=,x0=rand()%x,y=x0,k=;

     while (){

         i++;

         x0=(muti_mod(x0,x0,x)+c)%x;

         LL d=gcd(y-x0,x);

         if (d!= && d!=x){

             return d;

         }

         if (y==x0) return x;

         if (i==k){

             y=x0;

             k+=k;

         }

     }

 }

 //递归进行质因数分解N

 void findfac(LL n){

     if (!Miller_Rabin(n)){

         factor[tot++] = n;

         return;

     }

     LL p=n;

     while (p>=n) p=Pollard_rho(p,rand() % (n-) +);

     findfac(p);

     findfac(n/p);

 }

 int main(){

     int n;

     while(cin>>n){

         if(n == ){

             cout<<"no"<<endl;

             continue;

         }

         tot = ;

         findfac(n);

         bool ok = ;

         for(int i = ; i < tot; i++)

           if(factor[i] != factor[i-]){

               ok = ;

               break;

           }

         if(ok)cout<<"yes"<<endl;

         else cout<<"no"<<endl;

     }

     return ;

 }