判定输入的数是不是质数。
输入格式若干行，一行一个数 x。
行数不超过 1.5×104。
输出格式对于输入的每一行，如果 x 是质数输出一行 Y，否则输出一行 N。
样例样例输入1269666623333样例输出
NYNNY数据范围与提示
1≤x≤1018。
欢迎hack（如果你不是管理员，可以在题目讨论区发帖）。
Solution：
本题Miller-rabin模板题。
Miller-rabin其实是个很简单的算法，用来快速判断一个数是否为素数。
前置技能：二次探测定理。
若$a^2\equiv 1\mod p$且$p$为素数，则$a\equiv \pm 1\mod p$。
证明：$\because a^2\equiv 1\mod p$
$\therefore (a+1)(a-1)\equiv 0 \mod p$
又$p$为素数
$\therefore a=1$或$a=p-1$
我们由费马小定理，若$p$为素数，则$a^{p-1}\equiv 1 \mod p$，那么对于一个需要判断是否为素数的数$x$：
1、$x$必须是个非$1$的奇数。
2、令$x=2^k*c+1$（$c$为奇数），选择随机数$a$，使其满足所有$i<r$，都有$a^{2^i*c}\;mod\;p=p-1\;or\;1$。
然后就是模拟上述过程，多选几个随机数，若都能通过测试就是素数啦。
一般的话，随机选取4个数$2,3,5,7$，则在$2.5*10^{13}$以内唯一一个判断失误的数为$3215031751$。
然后细节就是当前数不能是所选取的随机数的倍数，否则会误判。
代码：
/*Code by 520 -- 9.10*/#include#define il inline#define ll long long#define RE register#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)using namespace std;const int cnt=3,tab[5]={2,3,7,61};ll n,m;ll Mul(ll x,ll y,ll mod){ ll ans=(x*y-(ll)((long double)x/mod*y+0.5)*mod); return ans<0?ans+mod:ans;}ll Exp(ll x,ll y,ll mod){ ll ans=1; while(y){ if(y&1) ans=Mul(ans,x,mod); y>>=1; x=Mul(x,x,mod); } return ans;}bool Miller_Rabin(ll &n){ if(n==2||n==3||n==5||n==7||n==11||n==61) return 1; if(n==1||n%2==0||n%3==0||n%5==0||n%7==0||n%11==0||n%61==0) return 0; For(i,0,cnt) { RE ll d=n-1; while(!(d&1)) d>>=1; RE ll s=Exp(tab[i],d,n); while(s!=1&&s!=n-1&&d!=n-1) d<<=1,s=Mul(s,s,n); if(s!=n-1&&!(d&1)) return 0; } return ����ҹ,��ҹ1;}int main(){ while(scanf("%lld",&n)!=EOF) putchar(Miller_Rabin(n)?'Y':'N'),putchar('\n'); return 0;}