如何判斷一個 16 位乃至更高位的整數是否為一個素數？

01-03

例如給出一個16位的大整數(用Q代替):12345678911121314
素數的定義:質數（prime number）又稱素數，有無限個。一個大於1的自然數，除了1和它本身外，不能被其他自然數整除（除0以外）的數稱之為素數（質數）[來自百度百科]
1.需要判斷的是這個數是否是一個偶數
2.循環使用一個N(N&3.在進一步-&>由定義可以簡化到X∈(2,√Q)的一個值域做除法運算即可

4.那麼值域裡面還存在可以被簡化的數(2的倍數)這些數也可以不考慮
5.問題: 最大化效率的情況下,如何思考這個Q是否是一個有效的素數?

這真的是一個很簡單的問題，但我實在看不下去目前這些回答的質量了……

1、素數判定是一個P問題，2004年已經被解決，詳見AKS primality test。

2、上面的確定性演算法並不夠實用，實踐中一般用概率性的Miller-Rabin Primality Test，多取幾個不同的基就可以使出錯概率非常小。

3.考慮到題主可能只是一個對數論感興趣的小朋友，我還是不要扯計算複雜性比較好。說一個簡單的演算法: 用2到根號Q之間的素數去試除即可，素數表可用篩法(請百度)獲得。

註：

1、僅用Fermat"s little theorem（即@夏華林的答案）不能剔除Carmichael number，無論換多少個基測的結果都是錯的，但Miller-Rabin Primality Test可以排除掉Carmichael number。

2、單純的試除法是一個偽多項式時間的演算法，因為時間複雜度是要把演算法的運行時間表示成輸入規模的多項式。如果輸入是數字N，那麼輸入的長度是O(lgN)，當某個演算法的運行時間是lgN的多項式時才是一個多項式時間的演算法。事實上，在討論這類題目時，一般文獻會用N表示輸入長度，或者說輸入數據的位數。

3、 @夏華林答案中的複雜度分析並不完全正確，因為它假定乘法、取模等操作是常數時間，這在N足夠大時不成立（不過在OI/ACM比賽中一般是成立的，數字一般都可以用64位的long long放下）。嚴謹的複雜度分析同樣參見維基百科Miller-Rabin Primality Test。

AKS, polynomial time;還有上面提到的一些

不過16位的數，用現在的計算機不需要這麼多複雜的演算法，little Fermat就夠了

=============

補充一下，謝謝 @運算元的提醒，little Fermat沒辦法剔除Carmichael數，不好意思

編製了個小程序測試19位數

for n in range(1033211111111111111,1033211111111111113):

for x in range(2,n):

if n%x==0:

print(n,"equals","*","n//x")

break

else :

print(n,"is a prime number")

1033211111111111111 equals * n//x

1033211111111111112 equals * n//x

這個問題看你到底是有個數吃不準還是想知道一般的演算法，吃不準可以去 Wolfram Alpha 上搜，直接輸入英語比如 is 11111111111 a prime? 就行了： is 11111111111 a prime?

要知道一般的演算法嘛，這個叫「素性測試」，有很多辦法，直接看維基百科即可：http://en.wikipedia.org/wiki/Primality_test

這個問題很有研究的價值。但是呢，一句話說不完，因為有的方法簡單，有的方法難。那麼既然有簡單的方法，為什麼用難的方法？回答只有一個——簡單的方法運行很慢。

最簡單的方法，在古希臘就知道了，叫做什麼埃拉托色尼斯篩法(Eratosthenes seive)，簡單到爆，不過也慢的要死。因為，它要進行O((n)^(1/2))次運算。

後來出現了費馬小定理，因此人們猜測，費馬小定理的逆命題成不成立啊——成立的話就是判定素性的另一種有效方法了——很可惜，不成立，341就是合數。但是不成立的數少得可憐，因此呢人們就起了一個挺好玩的名字，偽素數（卡邁爾數，Carmichael number）。既然你是16位的，那麼用這種方法就夠了——小於16位的卡邁爾數實在太少，再加上費馬小定理就夠了。

後來，人們發現了拉賓概率素性檢驗（Miller-Rabin Primality Test），但問題是如果它說這是合數，那沒得跑了，但如果說是素數，有一定概率這句話是錯的（要麼然幹嘛叫概率素性檢驗）——所以呢，還不完美。（這叫做啥Co-NP問題，我不太能解釋清楚，因為NP就需要解釋好久，再說解釋這個和我們的主題相差太多了）

在ERH（廣義黎曼假設）成立的條件下，有人（幸好我知道，這人叫做Miller，在1975年完成的）證明了存在一種相當快的演算法解決這個問題，有多快呢，大概是O((logn)^5)，嗯，真的相當快了。不過我擦，ERH成不成立估計幾百年都解決不了，這個有個P用。。。

現在問題來了，我要想快，就不一定準；要想准，就不一定快，咋辦咧？找更好的方法啊~

1983年三個人Leonard Adleman, Carl Pomerance, Robert Rumely給出了一個複雜度為O((logn)^(clogloglogn))的演算法——反正這是一個挺快的而且正確的東西——判斷一個100位的整數是不是素數只用幾毫秒——那麼對付16位的就更夠了啊。

沒玩呢，2002年，神奇的阿三們（M.Agrawal, N.Kayal, N.Saxena）給出了一個素性檢驗方法，能在O((logn)^12)內完成——我的天哪，這簡直就是奇蹟，而且如果索菲·熱爾曼素數密度假設（如果p是素數，那麼p+1也是素數）成立，指數能降到6——即便素數密度不成立，改進後的演算法也能滿足只比六次方高任意多的指數（就是O((logn)^(6+r))啦，r是任意實數）。

至於能不能找到更多的好的演算法，那就要看各位看到這篇回答的大神咯~反正我不認同這個問題被解決了，或許還有可能有更好的方法，或許廣義黎曼假設正確，然後新的演算法層出不窮呢~

多說一點，和這個問題很相關的是對於合數的質因數分解——這個問題比素性檢驗來得難得多，即便簡單的方法也很麻煩（這個應該是一個NP問題吧，雖然我不清楚，我只知道哈密頓迴路和求所有的主析取範式是NP的），比如說波拉德ρ檢驗，p檢驗（這倆真不是同一個字母），然後就是啥數域篩法、橢圓篩法之類的，麻煩的要死。

最後，附上那幾個印度人寫的論文，有空你可以看看，當然前提是要懂得一點數論和抽象代數的知識咯。那篇論文叫做PRIMES is in P，題目蠻好玩的。

Primes is in P.pdf_免費高速下載

很抱歉，我來晚了，詳細的看了cloak shining的回答，我非常認同，謝謝指出。

----------------------------------------

啊，終於有人贊了 ==。

===================================

運用費馬定理，對素數的判斷進行隨機化處理

用 Miller-Rabin 能確定性地在 X 是合數的時候給出它是合數；高概率地在 X 是素數的時候判斷出它是素數。

AKS 則是確定性的，但是速度比 Miller-Rabin 慢。

篩法.

A是2到[√Q]的整數

1.挑A中最小的元素x

2.x整除Q說明Q是合數

3.x不整除Q就刪去A中所有x的倍數

4.如果A中沒有元素了,說明Q是素數.否則回到第一步

大素數判斷沒什麼捷徑可走.

要真說改進,只能是在第二步那裡,有些tips可以用,比如fermat小定理

樓上提到的篩法和miller-rabin是信息學競賽中使用的toy級演算法。

真正的素性檢測是非常「困難」的問題，它與線性規劃，圖同構合成為三大最有希望歸類到P卻始終沒有找到「確定性」多項式演算法的問題。（其中圖同構已解決）

相關的研究與理論發展很快，詳細的方法可以參閱《演算法數論》之類的書籍。

看了一下，大家給的答案都是估算方法，我講一個準確方法，不是埃拉托色尼斯篩法。素數本身是沒有規律的，他的規律基於合數。以20為例，要求出小於20的素數的個數只要求合數個數就很容易得到。但是問題是會有許多重複的合數出現，比如15，他即會出現在20/3裡面，也會出現在20/5裡面，這樣就多算了一個合數，實際上數字越大，這樣的合數會越多，直接導致最終數值與真實數據天壤之別。但是這樣的重複合數也是有規律的。這個規律我要舉詳細的例子來說明：以20例，小於等於20的數中，

M1表示可以分解為n1*n1的有「2*2=4,3*3=9,4*4=16」3種方式，M2表示可以分解為n1*n2的有「2*3=6,2*4=8,2*5=10,2*6=12,2*7=14,2*8=16,2*9=18,2*10=20,

3*4=12,3*5=15,3*6=18,4*5=20」12種方式，

M3表示可以分解為n1*n1*n1的有「2*2*2=8」1種方式，M4表示可以分解為n1*n1*n2的有「2*2*3=12,2*2*4=16,2*2*5=20,3*3*2=18」4種方式，M5表示可以分解為n1*n2*n3的有0種方式，M6表示可以分解為n1*n1*n1*n1的有「2*2*2*2=16」1種方式，

n1*n1

M1=3

2*2=4,3*3=9,4*4=16

n1*n2

M2=12

2*3=6,2*4=8,2*5=10,2*6=12,2*7=14,2*8=16,2*9=18,2*10=20,3*4=12,3*5=15,3*6=18,4*5=20

n1*n1*n1

M3=1

2*2*2=8

n1*n1*n2

M4=4

2*2*3=12,2*2*4=16,2*2*5=20,3*3*2=18

n1*n2*n3

M5=0

n1*n1*n1*n1

M6=1

2*2*2*2=16

接下來把整數換成素數，得到下面的答案：

Q1表示可以分解為p1*p1的有「2*2=4,3*3=9」2種方式，Q2表示可以分解為p1*p2的有「2*3=6,2*5=10,2*7=14,3*5=15」4種方式，

Q3表示可以分解為p1*p1*p1的有「2*2*2=8」1種方式，Q4表示可以分解為p1*p1*p2的有「2*2*3=12,2*2*5=20,3*3*2=18」3種方式，Q5表示可以分解為p1*p2*p3的有0種方式，Q6表示可以分解為p1*p1*p1*p1的有「2*2*2*2=16」1種方式，

p1*p1

Q1=2

2*2=4,3*3=9

p1*p2

Q2=4

2*3=6,2*5=10,2*7=14,3*5=15

p1*p1*p1

Q3=1

2*2*2=8

p1*p1*p2

Q4=3

2*2*3=12,2*2*5=20,3*3*2=18

p1*p2*p3

Q5=0

p1*p1*p1*p1

Q6=1

2*2*2*2=16

M值與Q值的關係：M1=1*Q1+0*Q2+0*Q3+0*Q4+0*Q5+1*Q6=2+1=3 M2=0*Q1+1*Q2+1*Q3+2*Q4+3*Q5+1*Q6=4+1+6+1=12

M3=0*Q1+0*Q2+1*Q3+0*Q4+0*Q5+0*Q6=1

M4=0*Q1+0*Q2+0*Q3+1*Q4+0*Q5+1*Q6=4

M5=0*Q1+0*Q2+0*Q3+0*Q4+1*Q5+0*Q6=0

M6=0*Q1+0*Q2+0*Q3+0*Q4+0*Q5+1*Q6=1

當X為60時，

n1*n1

M1=6

2*2=4,3*3=9,4*4=16，5*5=25,6*6=36,7*7=49

n1*n2

M2=28+17+11+7+4+1=68

2*3=6,2*4=8,2*5=10,2*6=12,2*7=14,2*8=16,2*9=18,2*10=20,2*11=22,2*12=24,2*13=26,2*14=28,2*15=30,2*16=32,2*17=34,2*18=36,2*19=38,2*20=40,2*21=42,2*22=44,2*23=46,2*24=48,2*25=50,2*26-52,2*27=54,2*28=56,2*29=58,2*30=60，3*4=12,3*5=15,3*6=18,3*7=21,3*8=24,3*9=27,3*10=30,3*11=33,3*12=36,3*13=39,3*14=42,3*15=45,3*16=48,3*17=51,3*18=54,3*19=57,3*20=60,4*5=20,4*6=24,4*7=28,4*8=32,4*9=36,4*10=40,4*11=44,4*12=48,4*13=52,4*14=56,4*15=60,5*6=30,5*7=35,5*8=40,5*9=45,5*10=50,5*11=55,5*12=60,6*7=42,6*8=48,6*9=54,6*10=60,7*8=56

n1*n1*n1

M3=2

2*2*2=8,3*3*3=27

n1*n1*n2

M4=20

2*2*3=12,2*2*4=16,2*2*5=20,2*2*6=24,2*2*7=28,2*2*8=32,2*2*9=36,2*2*10=40,2*2*11=44,2*2*12=48,2*2*13=52,2*2*14=56,2*2*15=60，3*3*2=18，3*3*4=36，3*3*5=45，3*3*6=54,4*4*2=32,4*4*3=48,5*5*2=50

n1*n2*n3

M5=12

2*3*4=24,2*3*5=30,2*3*6=36,2*3*7=42,2*3*8=48,2*3*9=54,2*3*10=60,2*4*5=40,2*4*6=48,2*4*7=56，2*5*6=60，3*4*5=60

n1*n1*n1*n1

M6=1

2*2*2*2=16

n1*n1*n1*n2

M7=6

2*2*2*3=24,2*2*2*4=32,2*2*2*5=40,2*2*2*6=48,2*2*2*7=56,3*3*3*2=54

n1*n1*n2*n3

M8=2

2*2*3*4=48，2*2*3*5=60

n1*n2*n3*n4

M9=0

n1*n1*n2*n2

M10=1

2*2*3*3=36

n1*n1*n1*n1*n1

M11=1

2*2*2*2*2=32

n1*n1*n1*n1*n2

M12=1

2*2*2*2*3=48

接下來把整數換成素數，得到下面的答案：

p1*p1

Q1=4

2*2=4,3*3=9,5*5=25,7*7=49

p1*p2

Q2=17

2*3=6,2*5=10,2*7=14,2*11=22,2*13=26,2*17=34,2*19=38,2*23=46,2*29=58,3*5=15,3*7=21,3*11=33,3*13=39,3*17=51,3*19=57,5*7=35,5*11=55

p1*p1*p1

Q3=2

2*2*2=8,3*3*3=27

p1*p1*p2

Q4=8

2*2*3=12,2*2*5=20,,2*2*7=28,2*2*11=44,2*2*13=52,3*3*2=18,3*3*5=45,5*5*2=50

p1*p2*p3

Q5=2

2*3*5=30,2*3*7=42

p1*p1*p1*p1

Q6=1

2*2*2*2=16

p1*p1*p1*p2

Q7=4

2*2*2*3=24,2*2*2*5=40,2*2*2*7=56,3*3*3*2=54

p1*p1*p2*p3

Q8=1

2*2*3*5=60

p1*p2*p3*p4

Q9=0

p1*p1*p2*p2

Q10=1

2*2*3*3=36

p1*p1*p1*p1*p1

Q11=1

2*2*2*2*2=32

p1*p1*p1*p1*p2

Q12=1

2*2*2*2*3=48

M值與Q值的關係：M1=1*Q1+0*Q2+0*Q3+0*Q4+0*Q5+1*Q6+0*Q7+0*Q8+0*Q9+1*Q10+0*Q11+0*Q12=4+1+1=6 M2=0*Q1+1*Q2+1*Q3+2*Q4+3*Q5+1*Q6+3*Q7+5*Q8+7*Q9+3*Q10+2*Q11+4*Q12=17+2+16+6+1+12+5+3+2+4=68

M3=0*Q1+0*Q2+1*Q3+0*Q4+0*Q5+0*Q6+0*Q7+0*Q8+0*Q9+0*Q10+0*Q11+0*Q12=2

M4=0*Q1+0*Q2+0*Q3+1*Q4+0*Q5+1*Q6+1*Q7+1*Q8+0*Q9+2*Q10+2*Q11+2*Q12=8+1+4+1+2+2+2=20

M5=0*Q1+0*Q2+0*Q3+0*Q4+1*Q5+0*Q6+1*Q7+3*Q8+0*Q9+1*Q10+0*Q11+2*Q12=2+4+3+1+2=12

M6=0*Q1+0*Q2+0*Q3+0*Q4+0*Q5+0*Q6+0*Q7+0*Q8+0*Q9+0*Q10+0*Q11+0*Q12=1

M7=0*Q1+0*Q2+0*Q3+0*Q4+0*Q5+0*Q6+1*Q7+0*Q8+0*Q9+0*Q10+1*Q11+1*Q12=4+1+1=6

M8=0*Q1+0*Q2+0*Q3+0*Q4+0*Q5+0*Q6+0*Q7+1*Q8+0*Q9+0*Q10+0*Q11+1*Q12=1+1=2

M9=0*Q1+0*Q2+0*Q3+0*Q4+0*Q5+0*Q6+0*Q7+0*Q8+1*Q9+0*Q10+0*Q11+0*Q12=0

M10=0*Q1+0*Q2+0*Q3+0*Q4+0*Q5+0*Q6+0*Q7+0*Q8+0*Q9+1*Q10+0*Q11+0*Q12=1

M11=0*Q1+0*Q2+0*Q3+0*Q4+0*Q5+0*Q6+0*Q7+0*Q8+0*Q9+0*Q10+1*Q11+0*Q12=1

M12=0*Q1+0*Q2+0*Q3+0*Q4+0*Q5+0*Q6+0*Q7+0*Q8+0*Q9+0*Q10+0*Q11+1*Q12=1

M值是關於所有連續整數的函數，可以準確計算，Q值是關於所有連續素數的函數，M值與Q值的等式中，不難發現：係數是唯一的，無限的。利用這個唯一不變的係數和準確的M值，就可以準確計算素數個數、孿生素數個數以及素數對數個數。

miller-rabin

首先正如其他答主所說，這個問題是p問題，就是那個aks的，好像是印度人給出，但速度不夠快，實際應用中有更好的演算法，比如miller rabin演算法，這是一個概率演算法，如果它判定一個數是素數，那麼這個數是素數的概率大於或者等於四分之三，如果判定為合數則一定是合數。這兩個演算法所用到的知識不是很深，之需要初等數論和抽象代數知識就可以了，看懂前面的aks那個演算法需要一點有限域的知識。