作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我写了一个埃拉托斯特尼筛法——我想——但它似乎没有达到应有的优化程度。它有效,并且它得到了 N 以内的所有素数,但没有我希望的那么快。我仍在学习 Python(已经学了两年 Java),所以如果某些内容不是特别 Pythonic,那么我深表歉意:
def sieve(self):
is_prime = [False, False, True, True] + [False, True] * ((self.lim - 4) // 2)
for i in range(3, self.lim, 2):
if i**2 > self.lim: break
if is_prime[i]:
for j in range(i * i, self.lim, i * 2):
is_prime[j] = False
return is_prime
我看过与此类似的其他问题,但我无法弄清楚一些更复杂的优化如何适合我的代码。有什么建议吗?
编辑:根据要求,我看到的其他一些优化是在限制之前停止第一个 for 循环的迭代,并跳过不同的数字 - 我认为这是轮优化?
编辑 2:以下是针对 Padraic 使用该方法的代码:
primes = sieve.sieve()
for i in range(0, len(primes)):
if primes[i]:
print("{:d} ".format(i), end = '')
print() # print a newline
最佳答案
稍微不同的方法:使用位数组来表示奇数3,5,7,...
与 bool 值列表相比,节省一些空间。
这可能只会节省一些空间,而无助于加速...
from bitarray import bitarray
def index_to_number(i): return 2*i+3
def number_to_index(n): return (n-3)//2
LIMIT_NUMBER = 50
LIMIT_INDEX = number_to_index(LIMIT_NUMBER)+1
odd_primes = bitarray(LIMIT_INDEX)
# index 0 1 2 3
# number 3 5 7 9
odd_primes.setall(True)
for i in range(LIMIT_INDEX):
if odd_primes[i] is False:
continue
n = index_to_number(i)
for m in range(n**2, LIMIT_NUMBER, 2*n):
odd_primes[number_to_index(m)] = False
primes = [index_to_number(i) for i in range(LIMIT_INDEX)
if odd_primes[i] is True]
primes.insert(0,2)
print('primes: ', primes)
同样的想法又来了;但这一次让 bitarray 使用切片分配来处理内部循环。这可能会更快。
for i in range(LIMIT_INDEX):
if odd_primes[i] is False:
continue
odd_primes[2*i**2 + 6*i + 3:LIMIT_INDEX:2*i+3] = False
(此代码均未经过认真检查!请谨慎使用)
<小时/>如果您正在寻找基于不同方法的素数生成器( wheel factorizaition ),请查看 this excellent answer .
关于python-3.x - 进一步优化埃拉托斯特尼筛,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31120986/
我是一名优秀的程序员,十分优秀!