判定输入的数是不是质数。
Input
若干行，一行一个数 xx。
行数不超过 105105。
Output
对于输入的每一行，如果 xx 是质数输出一行 YY，否则输出一行 NN。
样例输入
1
2
6
9
666623333
样例输出
N
Y
N
N
Y思路：模板：https://blog.csdn.net/queque_heiya/article/details/105928679
注意：模板中只是循环了5次，测试数据中有两组数据没过，S=10即可；for(i=0;i<10;i++)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL mul_mod(LL a,LL b,LL mod){LL ret=0;while(b){if(b&1) ret=ret+a;if(ret>=mod) ret-=mod;a=a+a;if(a>=mod) a-=mod;b>>=1;}return ret;
}
LL pow_mod(LL a,LL b,LL mod){LL ret=1;while(b){if(b&1)ret=mul_mod(ret,a,mod);a=mul_mod(a,a,mod);b>>=1;}return ret;
}
bool Miller_Rabin(LL n){//判断素数 LL u=n-1,pre,x;int i,j,k=0;if(n==2||n==3||n==5||n==7||n==11) return true;if(n==1||(!(n%2))||(!(n%3))||(!(n%5))||(!(n%7))||(!(n%11))) returnfalse;//初始化判断素数 for(;!(u&1);k++,u>>=1);//按照要求转换形式 for(i=0;i<10;i++){x=rand()%(n-2)+2;//生成随机数 x=pow_mod(x,u,n);pre=x;for(j=0;j<k;j++){x=mul_mod(x,x,n);if(x==1&&pre!=1&&pre!=(n-1))//二次探测判断 return false;pre=x;}if(x!=1) return false;//用费马小定理判断 }return true;
}
int main(){LL n;while(scanf("%lld",&n)!=EOF){if(Miller_Rabin(n)) puts("Y");else puts("N");}return 0;
}