rt，Miller_Rabin 板题，照着 OIwiki 的思路码的，但是 61pts。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int qpow(int x,int y,int mod){
	int ans=1;
	while(y>0){
		if(y&1) ans=(ans*x)%mod;
		y>>=1;
		x=(x*x)%mod;
	}
	return ans;
}
int qmul(int x,int y,int mod){return (x*y-(long long)(x/(long double)mod*y+1e-3)*mod+mod)%mod;}
bool Miller_Rabin(int n){
    if(n<3||n%2==0) return n==2;
    int t=0,u=n-1;
    while(u%2==0){
        u=u/2;
        t++;
    }
    for(int i=0;i<16;i++){
        int a=rand()%(n-2)+2,v=qpow(a,u,n);
        if(v==1) continue;
        int s;
        for(s=0;s<t;s++){
            if(v==n-1) break;
            v=qmul(v,v,n);
        }
        if(s==t) return 0;
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while(cin>>n){
        if(Miller_Rabin(n)) cout<<"Y\n";
        else cout<<"N\n";
    }
    return 0;
}