#include <iostream>
#define int long long
using namespace std;
int pow(int a,int b,int p){
    int ans=1;
    while(b!=0){
        if(b%2==1) ans=ans*a%p;
        a=a*a%p,b/=2;
    }
    return ans;
}
bool pr(int x){
    if(x==0||x==1) return false;
    if(x==2) return true;
    const int chk[8]={0,2,325,9375,28178,450775,9780504,1795265022};
    for(int i=1;i<=8;i++){
        if(pow(chk[i],x,x)!=chk[i]%x){
            cout<<chk[i]%x<<"!="<<pow(chk[i],x,x)<<":";
            return false;
        }
    }
    return true;
}
signed main(){
    int x;
    while(cin>>x){
        if(pr(x)) cout<<"Y"<<endl;
        else cout<<"N"<<endl;
    }
    return 0;
}

对于样例

1
2
6
9
666623333

每次样例跑一遍都不同。。。