试题B: 小蓝做实验
【问题描述】
小蓝很喜欢科研，他最近做了一个实验得到了一批实验数据，一共是两百万个正整数。如果按照预期，所有的实验数据 x 都应该满足 10? ≤ x ≤ 10?。但是做实验都会有一些误差，会导致出现一些预期外的数据，这种误差数据 y 的范围是 103≤ y ≤ 1012 。由于小蓝做实验很可靠，所以他所有的实验数据中 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 = 0
while k < K:
b = int(random.random() * (p - 1) + 1)
factor = math.gcd(b, p)
r = runFermatPower(b, p, 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)
|