【問題描述】
小藍很喜歡科研，他最近做了一個實驗得到了一批實驗數據，一共是兩百萬個正整數。如果按照預期，所有的實驗數據 x 都應該滿足 10⁷ ≤ x ≤ 10⁸。但是做實驗都會有一些誤差，會導致出現一些預期外的數據，這種誤差數據 y 的范圍是 10³≤ y ≤ 10¹² 。由於小藍做實驗很可靠，所以他所有的實驗數據中 99.99% 以上都是符合預期的。小藍的所有實驗數據都在 primes.txt 中，現在他想統計這兩百萬個正整數中有多少個是質數，你能告訴他嗎？
【答案提交】
這是一道結果填空的題，你只需要算出結果後提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。
【思路分析】
臨到最後了這道題才想出來怎麼做，，，沒交上去，虧了
這個題有200w個數，直接暴力找肯定不行。我一開始走了彎路子，多線程，素數判斷優化都用上了。最後才發現我想多了，比賽結束前1分鐘才把數爆出來，也沒時間寫針對大數的素性測試了。。思路如下：
首先觀察數據，均以1、3、5、7結尾。大於1000且結尾為5的數，肯定能被5整除，於是先利用編輯器正則替換所有以5結尾的數，此時剩下約150w多個數：
\d+?5
使用埃氏篩選法，獲得10^8以內的所有質數，這裡注意，利用埃氏篩選法需要進行優化，不然也是跑的頭大。我在之前博客裡也寫過直接判斷質數的優化方法，除了2、3，所有質數均位於6n左右。因此可以直接將埃氏篩選法的步長拉到6，這樣速度能進一步提升，然後影響埃氏篩選法速度的大頭主要是2、3、5，需要進行多次循環才能篩掉後邊的合數，因此預處理在生成列表時直接將2、3、5的倍數歸0。理論上直接歸零的質數倍數越多，生成素數就越快。
計數質數 Python 埃氏篩選法_AYO_YO的博客-CSDN博客
判斷質數 Python Java C++_AYO_YO的博客-CSDN博客
def getprimes(n):
ls = [i if i % 2 != 0 and i % 3 != 0 and i % 5 != 0 else 0 for i in range(n + 1)]
ls[1], ls[2], ls[3], ls[5] = 0, 2, 3, 5
for i in range(6, n + 1, 6):
f = i - 1
if f != 0:
for j in range(2 * f, n + 1, f):
ls[j] = 0
continue
f = i + 1
if f != 0:
for j in range(2 * f, n + 1, f):
ls[j] = 0
return filter(lambda x: x != 0, ls)
埃氏篩選法篩選 1 0 8 10^8 108以內的質數大概需要2分鐘左右，再大恐怕就難以承受了。於是先將 1 0 8 10^8 108的質數統計出來，並把大於 1 0 8 10^8 108的質數拎出來。得到結果 1 0 8 10^8 108以內的質數有506733個。大數有約130個。
506733
[542693491967, 142787902577, 452440529173, 663634895869, 71242929179, 999870483413, 441673697183, 895134836909, 59008094959, 812048153483, 153230177243, 5986461211, 825268545161, 85386152959, 305669636917, 176618331487, 627185459239, 517233054923, 347714268719, 75380450897, 652349118967, 746710276723, 887316078643, 55623754253, 726602124691, 63723051253, 11944000489, 14326008041, 995344474081, 127374806651, 101228446879, 782792370337, 7616731547, 672817895497, 309261587441, 993510068537, 898280626321, 691250724803, 436362423451, 135244424501, 873959450791, 404517752423, 803431472291, 890481756773, 299729772337, 993254812121, 939705423281, 928689411767, 950796808643, 925182899009, 867933942403, 177084914339, 374154056921, 195931411013, 636268614181, 845966263637, 669349089677, 279219681547, 116772294307, 458677064359, 414099720659, 553029935971, 225122592047, 523383194647, 291752440213, 29190046721, 756126896941, 400963923179, 807339716593, 666619632839, 792597812483, 157223341237, 515677221383, 869902952023, 277744493561, 279840195947, 12066121523, 659914745389, 796743912131, 973038777059, 856703807231, 66169702601, 987064845247, 916671221021, 884623305749, 504935549881, 232438712231, 701919604183, 542037833447, 521942095081, 726449610001, 840499018589, 492469281101, 757165962919, 437417377471, 903288533789, 254110134101, 265121359891, 776841707227, 854559132599, 325401328397, 675731682791, 730947154187, 280786162939, 670729451441, 48996391291, 286681507897, 847973529401, 166381727761, 568868879153, 56085663143, 417414542761, 666771906149, 857635614683, 188918440631, 490214446741, 82741563491, 411523187461, 304024439243, 912661149107, 556591023551, 934801057481, 828742723319, 814141769183, 528476615281, 560425065263, 224638484077, 610321268093, 655599334577, 624348698849]
這些大數直接判斷是否是質數也是相當恐怖的，於是判斷特大數是否是質數，就要用另一個方法——費馬素性測試。這個是我之前算法課期末作業研究過的一個算法，就是利用隨機數隨機對大數取余，如果能整除，就不是質數；加入了一個優化，加入了一個互質判斷，大大提升了算法效率以及准確率。
for p in bigNum:
K = 100 # 取隨機數驗證的次數，該次數越大，准確率越高。實測K=10就能得到准確結果了
k = 0
while k < K: # 這裡用while是後續判定隨機完成率是否是100%
b = int(random.random() * (p - 1) + 1) # 生成一個1~p-1之間的隨機整數
factor = math.gcd(b, p) # 計算b,p的最大公約數
r = runFermatPower(b, p, p) # 計算b^p mod p
print(f"第{
k + 1}次取隨機數, 隨機數b={
b}, {
b}和{
p}的最大公約數為{
factor}, r=({
b}^{
p})mod p={
r}", end=', ')
if factor > 1:
print(f"因b={
b}與p={
p}的最大公約數為{
factor}，不為互質數，故p={
p}為合數")
break
elif r != b:
print(f"因r={
r},({
b}^{
p}) mod p ={
r}!={
b}, 故p={
p}為合數")
break
else:
print(f"故p={
p}可能為素數")
k += 1
if k == K:
print(f"經過{
K}次循環驗證, p={
p}可能為素數, n為素數的概率為{
(1 - 1 / (2 ** k)) * 100}%")
得到最終結果：
506753
【完整代碼】
比賽過程中的代碼是分步驟的，一步步寫，然後得到結果後再計算下一步，這個代碼是優化過的完整版代碼，直接運行就能得到最終結果。
B.py · AYO/Algorithm - 碼雲 - 開源中國 (gitee.com)
