1樓：
看了一下，大家給的答案都是估算方法，我講乙個準確方法，不是埃拉託色尼斯篩法。素數本身是沒有規律的，他的規律基於合數。以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
M值是關於所有連續整數的函式，可以準確計算，Q值是關於所有連續素數的函式，M值與Q值的等式中，不難發現：係數是唯一的，無限的。利用這個唯一不變的係數和準確的M值，就可以準確計算素數個數、孿生素數個數以及素數對數個數。
2樓：abcd
首先正如其他答主所說，這個問題是p問題，就是那個aks的，好像是印度人給出，但速度不夠快，實際應用中有更好的演算法，比如miller rabin演算法，這是乙個概率演算法，如果它判定乙個數是素數，那麼這個數是素數的概率大於或者等於四分之三，如果判定為合數則一定是合數。這兩個演算法所用到的知識不是很深，之需要初等數論和抽象代數知識就可以了，看懂前面的aks那個演算法需要一點有限域的知識。
3樓：Belleve
用 Miller-Rabin 能確定性地在 X 是合數的時候給出它是合數；高概率地在 X 是素數的時候判斷出它是素數。
AKS 則是確定性的，但是速度比 Miller-Rabin 慢。
4樓：莫濤
樓上提到的篩法和miller-rabin是資訊學競賽中使用的toy級演算法。
真正的素性檢測是非常「困難」的問題，它與線性規劃，圖同構合成為三大最有希望歸類到P卻始終沒有找到「確定性」多項式演算法的問題。（其中圖同構已解決）
相關的研究與理論發展很快，詳細的方法可以參閱《演算法數論》之類的書籍。
5樓：王盛頤
這個問題看你到底是有個數吃不準還是想知道一般的演算法，吃不準可以去 Wolfram Alpha 上搜，直接輸入英語比如 is 11111111111 a prime? 就行了： is 11111111111 a prime?
要知道一般的演算法嘛，這個叫「素性測試」，有很多辦法，直接看維基百科即可：http://
en.wikipedia.org/wiki/Primality_test
如何判斷乙個工作的價效比？
阿典 請問半佛，這思維模式或者說法方式太半佛了 半佛 應屆生求職利益最大化指南 嗶哩嗶哩 乾杯 bilibili 半佛 如何把自己賣個好價錢。嗶哩嗶哩 乾杯 bilibili 我沒法判斷，因為我沒有那麼多offer 半佛 不要成為全職家庭婦女，風險太高了。嗶哩嗶哩 乾杯 bilibili 錢多事少離...
如何判斷乙個畫室的好壞
果醬 在選擇畫室時確實需要了解清楚，因為有時侯選擇大於努力，判斷乙個畫室的好壞主要從這幾方面去考量，一是辦學時間，辦學時間久說明辦學經驗會比較豐富，還有近幾年的考學成績及發展趨勢，乙個畫室好壞的最關鍵體現就是考學成績，因為這是對學生和家長最好的回報，還有就是發展趨勢，如果近幾年畫室一直在變大說明口碑...
如何判斷乙個渣女？
親身經歷告訴你們，網上很多教你們鑑別渣女的方法都是片面的，狹隘的，碰到真正的渣女虐成灰真的，我就說一點吧，渣女不一定騙錢，她只是想得到她想要的就行。我曾經也被渣女騙感情過，乙個學妹，主動找我學鋼琴，他各種和我曖昧，投懷送抱，就希望我多抽出時間教教她，她還給我主動買了杯茶顏，你能說他不渣嗎？他想獲得的...