轉(zhuǎn)載自Matrix大牛
　　一個數(shù)是素數(shù)（也叫質(zhì)數(shù)）高镐，當且僅當它的約數(shù)只有兩個——1和它本身。規(guī)定這兩個約數(shù)不能相同，因此1不是素數(shù)挂滓。對素數(shù)的研究屬于數(shù)論范疇，你可以 看到許多數(shù)學家沒事就想出一些符合某種性質(zhì)的素數(shù)并稱它為某某某素數(shù)啸胧。整個數(shù)論幾乎就圍繞著整除和素數(shù)之類的詞轉(zhuǎn)過去轉(zhuǎn)過來杂彭。對于寫代碼的人來說墓毒，素數(shù)比 想像中的更重要，Google一下BigPrime或者big_prime你總會發(fā)現(xiàn)大堆大堆用到了素數(shù)常量的程序代碼亲怠。平時沒事時可以記一些素數(shù)下來以 備急用所计。我會選一些好記的素數(shù)，比如4567, 124567, 3214567, 23456789, 55566677, 1234567894987654321, 11111111111111111111111 (23個1)团秽。我的手機號前10位是個素數(shù)主胧。我的網(wǎng)站域名的ASCII碼連起來(77 97 116 114 105 120 54 55 46 99 111 109)也是個素數(shù)。
　　素數(shù)有很多神奇的性質(zhì)习勤。我寫5個在下面供大家欣賞踪栋。
1. 素數(shù)的個數(shù)無限多（不存在最大的素數(shù)）
　　證明：反證法，假設存在最大的素數(shù)P图毕，那么我們可以構(gòu)造一個新的數(shù)2 * 3 * 5 * 7 * … * P + 1（所有的素數(shù)乘起來加1）夷都。顯然這個數(shù)不能被任一素數(shù)整除（所有素數(shù)除它都余1），這說明我們找到了一個更大的素數(shù)予颤。
2. 存在任意長的一段連續(xù)數(shù)囤官，其中的所有數(shù)都是合數(shù)（相鄰素數(shù)之間的間隔任意大)
　　證明：當0<a<=n時，n!+a能被a整除蛤虐。長度為n-1的數(shù)列n!+2, n!+3, n!+4, …, n!+n中党饮，所有的數(shù)都是合數(shù)。這個結(jié)論對所有大于1的整數(shù)n都成立驳庭，而n可以取到任意大刑顺。
3. 所有大于2的素數(shù)都可以唯一地表示成兩個平方數(shù)之差。
　　 證明：大于2的素數(shù)都是奇數(shù)饲常。假設這個 數(shù)是2n+1蹲堂。由于(n+1)^ 2=n^2 + 2n+1，(n+1)^ 2和n^2就是我們要找的兩個平方數(shù)贝淤。下面證明這個方案是唯一的贯城。如果素數(shù)p能表示成 a^2-b2，則p=a^2- b^2=(a+b)(a-b)霹娄。由于p是素數(shù)能犯，那么只可能a+b=p且a-b=1，這給出了a和b的唯一解犬耻。
4. 當n為大于2的整數(shù)時踩晶，2 ^n +1和2^n-1兩個數(shù)中，如果其中一個數(shù)是素數(shù)枕磁，那么另一個數(shù)一定是合數(shù)渡蜻。
　　 證明：2^ n不能被3整除。如果它被3除余1，那么2^n -1就能被3整除茸苇；如果被3除余2排苍，那么2^n +1就能被3整除⊙埽總之淘衙，2^n +1和2^n -1中至少有一個是合數(shù)。
5. 如果p是素數(shù)腻暮，a是小于p的正整數(shù)彤守，那么a^(p-1) mod p = 1。
　　這個證明就有點麻煩了哭靖。
　　首先我們證明這樣一個結(jié)論：如果p是一個素數(shù)的話具垫，那么對任意一個小于p的正整數(shù)a，a, 2a, 3a, …, (p-1)a除以p的余數(shù)正好是一個1到p-1的排列试幽。例如筝蚕，5是素數(shù)，3, 6, 9, 12除以5的余數(shù)分別為3, 1, 4, 2铺坞，正好就是1到4這四個數(shù)起宽。
　　反證法，假如結(jié)論不成立的話康震，那么就是說有兩個小于p的正整數(shù)m和n使得na和ma除以p的余數(shù)相同。不妨假設n>m宾濒，則p可以整除a(n-m)腿短。但p是素數(shù)，那么a和n-m中至少有一個含有因子p绘梦。這顯然是不可能的橘忱，因為a和n-m都比p小。
　　 用同余式表述卸奉，我們證明了：
　　(p-1)! ≡ a * 2a * 3a * … * (p-1)a (mod p)
　　 也即：
　　(p-1)! ≡ (p-1)! * a^(p-1) (mod p)
　　兩邊同時除以(p-1)!钝诚，就得到了我們的最終結(jié)論：
　　1 ≡ a^(p-1) (mod p)
　可惜最后這個定理最初不是我證明的。這是大數(shù)學家Fermat證明的榄棵，叫做Fermat小定理(Fermat's Little Theorem)凝颇。Euler對這個定理進行了推廣，叫做Euler定理疹鳄。Euler一生的定理太多了拧略，為了和其它的“Euler定理”區(qū)別開來，有些地 方叫做Fermat小定理的Euler推廣瘪弓。Euler定理中需要用一個函數(shù)f(m)垫蛆，它表示小于m的正整數(shù)中有多少個數(shù)和m互素（兩個數(shù)只有公約數(shù)1稱 為互素）。為了方便，我們通常用記號φ(m)來表示這個函數(shù)（稱作Euler函數(shù)）袱饭。Euler指出川无，如果a和m互素，那么a^φ(m) ≡ 1 (mod m)虑乖∨城鳎可以看到，當m為素數(shù)時决左，φ(m)就等于m-1（所有小于m的正整數(shù)都與m互素）愕够，因此它是Fermat小定理的推廣。定理的證明和Fermat小 定理幾乎相同佛猛，只是要考慮的式子變成了所有與m互素的數(shù)的乘積：m_1 * m_2 … m_φ(m) ≡ (a * m_1)(a * m_2) … (a * m_φ(m)) (mod m)惑芭。我為什么要順便說一下Euler定理呢？因為下面一句話可以增加我網(wǎng)站的PV：這個定理出現(xiàn)在了The Hundred Greatest Theorems里继找。
　　談到Fermat小定理遂跟，數(shù)學歷史上有很多誤解。很長一段時間里婴渡，人們都認為Fermat小定理的逆命題是正確的幻锁，并且有人親自驗證了 a=2, p<300的所有情況。國外甚至流傳著一種說法边臼，認為中國在孔子時代就證明了這樣的定理：如果n整除2^(n-1)-1哄尔，則n就是素數(shù)。后來某個英 國學者進行考證后才發(fā)現(xiàn)那是因為他們翻譯中國古文時出了錯柠并。1819年有人發(fā)現(xiàn)了Fermat小定理逆命題的第一個反例：雖然2的340次方除以341余 1岭接，但341=11*31。后來臼予，人們又發(fā)現(xiàn)了561, 645, 1105等數(shù)都表明a=2時Fermat小定理的逆命題不成立鸣戴。雖然這樣的數(shù)不多，但不能忽視它們的存在粘拾。于是窄锅，人們把所有能整除2^(n-1)-1的合 數(shù)n叫做偽素數(shù)(pseudoprime)，意思就是告訴人們這個素數(shù)是假的缰雇。
　　不滿足2^(n-1) mod n = 1的n一定不是素數(shù)入偷；如果滿足的話則多半是素數(shù)。這樣械哟，一個比試除法效率更高的素性判斷方法出現(xiàn)了：制作一張偽素數(shù)表盯串，記錄某個范圍內(nèi)的所有偽素數(shù)，那么 所有滿足2^(n-1) mod n = 1且不在偽素數(shù)表中的n就是素數(shù)戒良。之所以這種方法更快体捏，是因為我們可以使用二分法快速計算2^(n-1) mod n 的值，這在計算機的幫助下變得非常容易；在計算機中也可以用二分查找有序數(shù)列几缭、Hash表開散列河泳、構(gòu)建Trie樹等方法使得查找偽素數(shù)表效率更高。
　　 有 人自然會關心這樣一個問題：偽素數(shù)的個數(shù)到底有多少年栓？換句話說拆挥，如果我只計算2^(n-1) mod n的值，事先不準備偽素數(shù)表某抓，那么素性判斷出錯的概率有多少纸兔？研究這個問題是很有價值的，畢竟我們是OIer否副，不可能背一個長度上千的常量數(shù)組帶上考場汉矿。 統(tǒng)計表明，在前10億個自然數(shù)中共有50847534個素數(shù)备禀，而滿足2^(n-1) mod n = 1的合數(shù)n有5597個洲拇。這樣算下來，算法出錯的可能性約為0.00011曲尸。這個概率太高了赋续，如果想免去建立偽素數(shù)表的工作，我們需要改進素性判斷的算 法另患∨β遥　
　　 最簡單的想法就是，我們剛才只考慮了a=2的情況昆箕。對于式子a^(n-1) mod n鸦列，取不同的a可能導致不同的結(jié)果。一個合數(shù)可能在a=2時通過了測試为严，但a=3時的計算結(jié)果卻排除了素數(shù)的可能敛熬。于是肺稀，人們擴展了偽素數(shù)的定義第股，稱滿足 a^(n-1) mod n = 1的合數(shù)n叫做以a為底的偽素數(shù)(pseudoprime to base a)。前10億個自然數(shù)中同時以2和3為底的偽素數(shù)只有1272個话原，這個數(shù)目不到剛才的1/4夕吻。這告訴我們?nèi)绻瑫r驗證a=2和a=3兩種情況，算法出錯 的概率降到了0.000025繁仁。容易想到涉馅，選擇用來測試的a越多，算法越準確黄虱。通常我們的做法是稚矿，隨機選擇若干個小于待測數(shù)的正整數(shù)作為底數(shù)a進行若干次 測試，只要有一次沒有通過測試就立即把這個數(shù)扔回合數(shù)的世界。這就是Fermat素性測試晤揣。
　　人們自然會想桥爽，如果考慮了所有小于n的底數(shù)a，出錯的概率是否就可以降到0呢昧识？沒想 到的是钠四，居然就有這樣的合數(shù)，它可以通過所有a的測試（這個說法不準確跪楞，詳見我在地核樓層的回復）缀去。Carmichael第一個發(fā)現(xiàn)這樣極端的偽素數(shù)，他 把它們稱作Carmichael數(shù)甸祭。你一定會以為這樣的數(shù)一定很大缕碎。錯。第一個Carmichael數(shù)小得驚人淋叶，僅僅是一個三位數(shù)阎曹，561。前10億個自 然數(shù)中Carmichael數(shù)也有600個之多煞檩。Carmichael數(shù)的存在說明处嫌，我們還需要繼續(xù)加強素性判斷的算法。
　　Miller和Rabin兩個人的工作讓Fermat素性測試邁出了革命性的一步斟湃，建立了傳說中的Miller-Rabin素性測試算法熏迹。 新的測試基于下面的定理：如果p是素數(shù)，x是小于p的正整數(shù)凝赛，且x^2 mod p = 1注暗，那么要么x=1，要么x=p-1墓猎。這是顯然的捆昏，因為x^2 mod p = 1相當于p能整除x^2-1，也即p能整除(x+1)(x-1)毙沾。由于p是素數(shù)骗卜，那么只可能是x-1能被p整除(此時x=1)或x+1能被p整除(此時 x=p-1)。
　　 我們下面來演示一下上面的定理如何應用在Fermat素性測試上左胞。前面說過341可以通過以2為底的Fermat測試寇仓，因 為2^ 340 mod 341=1。如果341真是素數(shù)的話烤宙，那么2^ 170 mod 341只可能是1或340遍烦；當算得2^ 170 mod 341確實等于1時，我們可以繼續(xù)查看2^ 85除以341的結(jié)果躺枕。我們發(fā)現(xiàn)服猪，2^ 85 mod 341=32供填，這一結(jié)果摘掉了341頭上的素數(shù)皇冠，面具后面真實的嘴臉顯現(xiàn)了出來罢猪，想假扮素數(shù)和我的素MM交往的企圖暴露了出來捕虽。
　　 這就 是Miller-Rabin素性測試的方法。不斷地提取指數(shù)n-1中的因子2坡脐，把n-1表示成d*2^ r（其中d是一個奇數(shù)）泄私。那么我們需要計算的東西就 變成了a的d*2^ r次方除以n的余數(shù)。于是备闲，a^(d * 2^ (r-1))要么等于1晌端，要么等于n-1。如果a^(d * 2^ (r-1))等于1恬砂，定理繼續(xù)適用于a^(d * 2^ (r-2))咧纠，這樣不斷開方開下去，直到對于某個i滿足a^(d * 2^i) mod n = n-1或者最后指數(shù)中的2用完了得到的a^d mod n=1或n-1泻骤。
　　這樣漆羔，F(xiàn)ermat小定理加強為如下形式：
　　 盡可能提取因子2， 把n-1表示成d*2^r 狱掂，如果n是一個素數(shù)演痒，那么或者a^d mod n=1，或者存在某個i使得a^ (d*2^ i) mod n=n-1 ( 0<=i<r ) （注意i可以等于0趋惨，這就把a^d mod n=n-1的情況統(tǒng)一到后面去了）
　　 Miller-Rabin 素性測試同樣是不確定算法鸟顺，我們把可以通過以a為底的Miller-Rabin測試的合數(shù)稱作以a為底的強偽素數(shù)(strong pseudoprime)。第一個以2為底的強偽素數(shù)為2047器虾。第一個以2和3為底的強偽素數(shù)則大到1 373 653讯嫂。
　　Miller- Rabin算法的代碼也非常簡單：計算d和r的值（可以用位運算加速），然后二分計算a^d mod n的值兆沙，最后把它平方r次欧芽。
素數(shù)的性質(zhì)。

Miller-Rabin質(zhì)數(shù)測試
模板來源:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
//  計算(a * b) % mod
long long multiMod(long long a,long long b,long long mod)
{
    long long res=0;
    while(b)
    {
        if(b&1)
        {
            res=res+a;
            if(res>=mod) res-=mod;
        }
        a=a+a;
        if(a>=mod) a-=mod;
        b>>=1;
    }
    return res;
}
//  計算 (a ^ b) % mod
long long powMod(long long a,long long b,long long mod)
{
    long long res=1;
    while(b)
    {
        if(b&1)
        {
            res=multiMod(res,a,mod);
        }
        a=multiMod(a,a,mod);
        b>>=1;
    }
    return res;
}
//  通過a ^ (n - 1) = 1(mod n)來判斷n是不是素數(shù)
//  n - 1 = x * 2 ^ t中間使用二次判斷
//  是合數(shù)返回true葛圃，不一定是合數(shù)返回false
bool check(long long a,long long n,long long x,int t)
{
    long long res=powMod(a,x,n);
    long long last=res;
    for(int i=1;i<=t;i++)
    {
        res=multiMod(res,res,n);
        if(res==1&&last!=1&&last!=n-1) return true;//合數(shù)
        last=res;
    }
    return res!=1;//最后res=(a^(n-1) % n),如果res!=1,那么不滿足費小馬定理,說明不是素數(shù)
}
//  生成[ 0 , n ]的隨機數(shù)
long long randomVal(long long n)
{
    //rand(): 0~RAND_MAX;
    return ((double)rand()/RAND_MAX*n+0.5);
}
//  隨機算法判定次數(shù)千扔，一般8～10次就夠了
const int times=8;
//  Miller_Rabin算法
//  是素數(shù)返回true，（可能是偽素數(shù)）
//  不是素數(shù)返回false
bool Miller_Rabin(long long n)
{
    if(n<2) return false;
    if(n==2) return true;
    if(!(n&1)) return false;//  偶數(shù)（合數(shù)）
    long long x=n-1,t=0;
    while((x&1)==0)
    {
        t++;
        x>>=1;
    }
    for(int i=0;i<times;i++)
    {
        long long a=randomVal(n-2)+1;
        if(check(a,n,x,t)) return false;
    }
    return true;
}
int main()
{
    long long n,t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        if(Miller_Rabin(n)) printf("Yes\n");
        else printf("No\n");
    }
}