一.素數(shù)的一些性質(zhì)：
素數(shù)的個數(shù)無限多（不存在最大的素數(shù)）
存在任意長的一段連續(xù)數(shù)，其中的所有數(shù)都是合數(shù)（相鄰素數(shù)之間的間隔任意大）
所有大于2的素數(shù)都可以唯一地表示成兩個平方數(shù)之差。
（證明：大于2的素數(shù)都是奇數(shù)。假設(shè)這個數(shù)是2n+1。由于 (n+1)2 = n2+2n+1，(n+1)2和n2就是我們要找的兩個平方數(shù)。下面證明這個方案是唯一的。如果素數(shù)p能表示成a2-b2，則p=a2-b2=(a+b)(a-b)。由于p是素數(shù)，那么只可能a+b=p且a-b=1，這給出了a和b的唯一解。）
當n為大于2的整數(shù)時，2n+1和2n-1兩個數(shù)中，如果其中一個數(shù)是素數(shù)，那么另一個數(shù)一定是合數(shù)。
如果p是素數(shù)，a是小于p的正整數(shù)，那么a(p-1) mod p = 1。（費馬小定理）
二.單個判斷素數(shù)
大于等于5的質(zhì)數(shù)一定和6的倍數(shù)相鄰
#include <iostream>
#include <math.h>
using namespace std;
int isPrime(int n)
{ //返回1表示判斷為質(zhì)數(shù)，0為非質(zhì)數(shù)，在此沒有進行輸入異常檢測
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;
}
三.篩選素數(shù)
歐拉篩法
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;//篩數(shù)
if(i%prime[j]==0)//時間復雜度為O(n)的關(guān)鍵！
break;
}
}
}
用埃式篩法的同時，同一個數(shù)字也許會被篩選多次，比如6先被2篩選一次，再被3篩選一次，這樣就浪費了很多不必要的時間，而歐拉篩法通過if(i%prime[j]==0)break;這一步就避免了重復篩選的發(fā)生，我們舉個例子，比如，2先篩選了4，然后進行下一個循環(huán)，3篩選6和9，當我們執(zhí)行到4的時候，可以發(fā)現(xiàn)，當i==4時，第一次運行到if(i%prime[j]==0)這一步的時候就直接break;掉了，這也就是說，當我們的合數(shù)進入循環(huán)時，其實它已經(jīng)被之前的數(shù)篩選過了，所以當合數(shù)進入內(nèi)層循環(huán)時，內(nèi)層循環(huán)只執(zhí)行了一次，從而減少了時間復雜度。
比如：i=k x prime[j]； 我們?nèi)绻惶鲅h(huán)的話，繼續(xù)計算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)的關(guān)鍵！
break;
四.大素數(shù)判定（Miller-Rabin算法）
1.費馬小定理
a^p ≡ a (mod p)-->p為質(zhì)數(shù) 必要不充分
兩邊同除a得：
a^(p-1) ≡ 1 (mod p)
2.二次探測定理
如果（p為奇素數(shù)）的話，則有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為素數(shù)；
(2)步驟1不成立的話，使用二次探測
while(n-1 為偶數(shù)){
u = (n-1)/2;
套用二次探測
a^u ≡ 1 (mod n)?
a^u ≡ n-1 (mod n)?
}
(3)換用a，繼續(xù)算法，一般當n<2^64時，a一般選用前7個素數(shù)(2, 3, 5, 7, 11, 13和17)進行測試，所有不超過341 550 071 728 320的數(shù)都是正確的。
一般我們直接獲取隨機數(shù)就可以。
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;
}
