python - 如何在 Python 中优化这个 Mersenne Prime Sieve 的速度?
问题描述
我需要有关我为执行此任务而编辑的 Mersenne Prime Sieve 的帮助;这段代码来自一个完美的数字生成器。问题是程序在 python 中在 11213 处变慢。任何人都可以为这种筛子提供一些速度增强功能吗?输出是这样开始的。2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213
from itertools import count
def postponed_sieve(): # postponed sieve, by Will Ness
yield 2; yield 3; yield 5; yield 7; # original code David Eppstein,
sieve = {} # Alex Martelli, ActiveState Recipe
#2002
ps = postponed_sieve() # a separate base Primes Supply:
p = next(ps) and next(ps) # (3) a Prime to add to dict
q = p*p # (9) its sQuare
for c in count(9,2): # the Candidate
if c in sieve: # c's a multiple of some base prime
s = sieve.pop(c) # i.e. a composite ; or
elif c < q:
yield c # a prime
continue
else: #(c==q) # or the next base prime's square:
s=count(q+2*p,2*p) # (9+6, by 6 : 15,21,27,33,...)
p=next(ps) # (5)
q=p*p # (25)
for m in s: # the next multiple
if m not in sieve: # no duplicates
break
sieve[m] = s # original test entry: ideone.com/WFv4f
def prime_sieve(): # postponed sieve, by Will Ness
yield 2; yield 3; yield 5; yield 7; # original code David Eppstein,
sieve = {} # Alex Martelli, ActiveState Recipe
#2002
ps = postponed_sieve() # a separate base Primes Supply:
p = next(ps) and next(ps) # (3) a Prime to add to dict
q = p*p # (9) its sQuare
for c in count(9,2): # the Candidate
if c in sieve: # c’s a multiple of some base prime
s = sieve.pop(c) # i.e. a composite ; or
elif c < q:
yield c # a prime
continue
else: #(c==s) # or the next base prime’s square:
s=count(q+2*p,2*p) # (9+6, by 6 : 15,21,27,33,...)
p=next(ps) # (5)
q=p*p # (25)
for m in s: # the next multiple
if m not in sieve: # no duplicates
break
sieve[m] = s # original test entry: ideone.com/WFv4f
def mod_mersenne(n, prime, mersenne_prime):
while n > mersenne_prime:
n = (n & mersenne_prime) + (n >> prime)
if n == mersenne_prime:
return 0
return n
def is_mersenne_prime(prime, mersenne_prime):
s = 4
for i in range(prime - 2):
s = mod_mersenne((s*s - 2), prime, mersenne_prime)
return s == 0
def calculate_perfects():
yield(2)
primes = prime_sieve()
next(primes) #2 is barely even a prime
for prime in primes:
if is_mersenne_prime(prime, 2**prime-1):
yield(prime)
if __name__ == '__main__':
for perfect in calculate_perfects():
print(perfect)
#edited by Tom E. O'Neil to find Mprimes
解决方案
推荐阅读
- python - 保存/加载带有常量的 keras 模型
- angular - Angular/Typescript - 引用来自 REST 服务的属性中的对象数组
- maven - 如何获取maven项目dependencyManagement块中列出的pom(bom)的artifactId
- r - 使用 R 向 Leaflet 中的图层控制框添加标题
- android - 在 playStore 上提交被拒绝的应用程序
- android - Kotlin:滚动时隐藏/显示 BottomNavigationView
- javascript - Refreshing page with background video
- javascript - 是否可以进行双重替换?
- sql - 通过 SQL 删除 Wordpress 中所有未使用的类别
- mysql - 如何将 10 位数字存储到 sql bigint 数据类型中?