一.素数的一些性质：
素数的个数无限多（不存在最大的素数）
存在任意长的一段连续数，其中的所有数都是合数（相邻素数之间的间隔任意大）
所有大于2的素数都可以唯一地表示成两个平方数之差。
（证明：大于2的素数都是奇数。假设这个数是2n+1。由于 (n+1)2 = n2+2n+1，(n+1)2和n2就是我们要找的两个平方数。下面证明这个方案是唯一的。如果素数p能表示成a2-b2，则p=a2-b2=(a+b)(a-b)。由于p是素数，那么只可能a+b=p且a-b=1，这给出了a和b的唯一解。）
当n为大于2的整数时，2n+1和2n-1两个数中，如果其中一个数是素数，那么另一个数一定是合数。
如果p是素数，a是小于p的正整数，那么a(p-1) mod p = 1。（费马小定理）
二.单个判断素数
大于等于5的质数一定和6的倍数相邻
#include <iostream>
#include <math.h>
using namespace std;
int isPrime(int n)
{ //返回1表示判断为质数，0为非质数，在此没有进行输入异常检测
float n_sqrt;
if(n==2 || n==3) return 1;
if(n%6!=1 && n%6!=5) return 0;
n_sqrt=floor(sqrt((float)n));
for(int i=5;i<=n_sqrt;i+=6)
{
if(n%(i)==0 | n%(i+2)==0) return 0;
}
return 1;
}
int main()
{
int flag;
flag=isPrime(37);
cout<<flag<<endl;
return 0;
}
三.筛选素数
欧拉筛法
int prime[MAXN];
bool vis[MAXN];
int cnt=0;
void Euler_peime(int n)
{
for(int i=2;i<=n;++i)
{
if(!vis[i])
{prime[cnt++]=i;vis[i]=true;}//vis[i]置为true或不置true都可以
for(int j=0;j<cnt;++j)
{
if(i*prime[j]>n)//判断是否越界
break;
vis[i*prime[j]]=true;//筛数
if(i%prime[j]==0)//时间复杂度为O(n)的关键！
break;
}
}
}
用埃式筛法的同时，同一个数字也许会被筛选多次，比如6先被2筛选一次，再被3筛选一次，这样就浪费了很多不必要的时间，而欧拉筛法通过if(i%prime[j]==0)break;这一步就避免了重复筛选的发生，我们举个例子，比如，2先筛选了4，然后进行下一个循环，3筛选6和9，当我们执行到4的时候，可以发现，当i==4时，第一次运行到if(i%prime[j]==0)这一步的时候就直接break;掉了，这也就是说，当我们的合数进入循环时，其实它已经被之前的数筛选过了，所以当合数进入内层循环时，内层循环只执行了一次，从而减少了时间复杂度。
比如：i=k x prime[j]； 我们如果不跳出循环的话，继续计算prime[j+1]---->i x prime[j+1]=k x prime[j] x prime[j+1]；k x prime[j+1]会与i相等,于是式子就变成了i*prime[j]，会被第二次筛到，所以加上这个判断可以大大缩小复杂度。
if(i%prime[j]==0)//时间复杂度为O(n)的关键！
break;
四.大素数判定（Miller-Rabin算法）
1.费马小定理
a^p ≡ a (mod p)-->p为质数 必要不充分
两边同除a得：
a^(p-1) ≡ 1 (mod p)
2.二次探测定理
如果（p为奇素数）的话，则有x^2 ≡ 1 (mod p);
该方程有两组解：
(1)x ≡ 1 (mod p)
(2)x ≡ p-1 (mod p)
3.算法步骤
(1)先使用费马小定理 if(a^(n-1) ≡ 1 (mod n) ) 成立的话，就说明p为素数；
(2)步骤1不成立的话，使用二次探测
while(n-1 为偶数){
u = (n-1)/2;
套用二次探测
a^u ≡ 1 (mod n)?
a^u ≡ n-1 (mod n)?
}
(3)换用a，继续算法，一般当n<2^64时，a一般选用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试，所有不超过341 550 071 728 320的数都是正确的。
一般我们直接获取随机数就可以。
4.代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#define MOD n
#define LL long long
#define UP 5
using namespace std;
int m;
LL n;
LL qsc(LL a,LL b,LL mod){
LL sum = 0;
while(b){
if(b&1)sum=(sum+a)%mod;
a=(a+a)%mod;
b>>=1;
}return sum%mod;
}
LL pow(LL a,LL b,LL mod){
LL res = 1;
while(b){
if(b&1)res=qsc(res,a,mod);
a=qsc(a,a,mod);b>>=1;
}return res%mod;
}
bool MR(){
if(n==2)return true;
if( (!(n&1)) || n<2 )return false;
LL u=n-1,a,x,y;
while(!(u&1))u>>=1;
for(int i=0;i<1;++i){
a=rand()%(n-2)+2;
x=pow(a,u,n);int tmp=u;
while(u<n){
y=pow(x,2,n);
if(y==1&&x!=1&&x!=n-1)return false;
x=y;u*=2;
}u=tmp;
if(x!=1)return false;
}return true;
}
int main(){
srand(time(NULL));
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%lld",&n);
if(MR())printf("Yes\n");
else printf("No\n");
}return 0;
}
