进一步优化埃拉托色尼筛法

Question

我写了一个埃拉托色尼筛法——我想——但它似乎没有达到应有的优化程度。它起作用了，它得到了 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

Answer 1

一种略有不同的方法：使用位数组表示奇数 3,5,7,... 与布尔值列表相比节省了一些 space。

这可能只会节省一些 space 而无助于加速...

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

(此代码none已认真检查！谨慎使用)

如果您正在寻找基于不同方法的素数生成器 (wheel factorizaition) have a look at 。

进一步优化埃拉托色尼筛法

Optimize Sieve of Eratosthenes Further

optimization

primes

python-3.x