定义质数为因数只含1和其本身的数，对于N组询问，试判断每个数是否为素数。
第一行一个正整数N，表示有N组询问。
接下来N行，每行一个正整数M，表示询问M是否为质数。
输出N行，每行一个字符串。
若是质数则输出‘Prime’，若不是质数则输出‘Not prime’。
5
2
10
89807289
9032482948
1000000007
Prime
Not prime
Not prime
Not prime
Prime
样例解释：
10=25
89807289=3 11 * 11 * 13 * 19031
9032482948=2 * 2 * 439 * 5143783
20%的数据满足N≤100，1< M≤800,000。
50%的数据满足N≤1,000，1< M≤100,000,000。
100%的数据满足N≤1,000，1< M≤1,000,000,000,000.
显然，\(O(n\sqrt m)\)一定会T飞
1< M≤1,000,000,000,000.
Time Limits:2000 ms Memory Limits: 262144 KB
原因？？
因为我懒得弄，
其实应该差不多。
1.费马小定理
\(x^{p-1}\equiv 1 (mod\; p)\)
若 有很多的x 都满足，那p就极有可能
是一个质数
反之 如果有 \(x \ne p\)且不满足，一定是合数
2.分块乘
我只会分块乘，快速乘什么的不要说
\((ax+b)(cx+d)mod\; p=(acx^2+adx+bcx+bd)mod\;p\)
**豪同学狂言称霸10^18次方，
一到 某谷 某题上就萎了
所以伪Miller Rabin不要乱用
#include<cstdio>
#include<cstring>
using namespace std;
#define Np 12
int wp[Np]={0,2,3,5,7,11,13,17,19,23,29,31};
#define tmi 1048575ll
#define tty 1048576ll
#define tmr 1099511627776ll
inline long long supx(long long a,long long b,long long mod)
{
long long a0=a&tmi,a1=a>>20;
long long b0=b&tmi,b1=b>>20;
long long ans=((a1%mod)%mod*(b1*tmr%mod)%mod+a0*b0%mod)%mod;
ans=(ans+(a0*(b1%mod)%mod*(tty%mod)%mod)%mod)%mod;
ans=(ans+(b0*(a1%mod)%mod*(tty%mod)%mod)%mod)%mod;
return ans;
}
inline long long qpow(long long a,long long x,long long mod)
{
long long ans=1,apow=a;
while(x>0)
{
if(x&1) ans=supx(ans,apow,mod);
apow=supx(apow,apow,mod);
// printf(" %lld %lld\n",apow,ans);
x>>=1;
}
return ans;
}
int main()
{
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
int n,i,j;long long wpow,m;
bool ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&m);
ans=1;
for(j=1;j<Np;j++)
{
if(wp[j]!=m)
{
wpow=qpow(wp[j],m-1,m);
if(wpow!=1){ans=0;break;}
}
else break;
}
if(ans) printf("Prime\n");
else printf("Not prime\n");
}
return 0;
}
伪Miller Rabin—— JZOJ(GMOJ)4278. 【NOIP2015模拟10.29B组】质数
原文：https://www.cnblogs.com/JY-Chen/p/11382194.html