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

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

我查看过其他与此类似的问题，但是我无法弄清楚一些更复杂的优化如何适用于我的代码。有什么建议吗？

编辑：根据要求，我看到的一些其他优化是在达到限制之前停止第一个循环的迭代，以及通过不同的数字跳过循环--我认为这是轮子优化？

编辑2：这里是将使用该方法的代码，供Padraic参考：

primes = sieve.sieve()
for i in range(0, len(primes)):
    if primes[i]:
        print("{:d} ".format(i), end = '')
print() # print a newline

- user5062192

---

你能否简要地解释一下你提到的其他优化措施？ - BlackVegetable

第二个 if i ** 2 > self.lim: break 行是多余的。 - jwodder

@PadraicCunningham 嗯，索引要么是True要么是False。'is_prime[2]'将等于'True'。因此，2是质数。0索引是'False'，所以零不是质数。如果您想要，可以将其转换为整数列表。这是为了节省内存。 - user5062192

切片赋值是一种标准技术，可用于加速将多个设置为false的内部循环。我本来要打出答案，但简单的谷歌搜索就能找到比我更好的结果——例如，http://codereview.stackexchange.com/questions/42420/sieve-of-eratosthenes-python。 - sykora

你可以使用 range(i * i, self.lim, 2*i)。 - Will Ness

Answer 1

一个稍微不同的方法：使用位数组来表示奇数3,5,7,...相比布尔列表可以节省一些空间。

这可能只能节省一些空间，而不能帮助加速...

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

（此代码未经严格检查！请小心使用）

---

如果你正在寻找基于不同方法（轮子分解）的质数生成器，请看看这个优秀的答案。

- hiro protagonist

---

这实际上是一个非常有趣的方法。肯定可以节省空间。 - user5062192

我尝试将您的解决方案与其他解决方案集成，并得出了一种似乎运行良好的组合。我的原始算法对于1,000,000需要大约800毫秒。我的新算法取决于您如何操作。如果您使用位数组（未经过优化只能处理奇数），则需要大约200毫秒。速度有所提升，但真正的好处在于其内存占用基本上不存在（使用sys.getsizeof()）。如果您改用布尔数组，则需要大约60-80毫秒。 - user5062192

个人而言，我更喜欢n=2i+1的寻址方案（以浪费一个内存单元为代价），因为它允许使用漂亮的闭合形式进行索引：对于第i个条目，其值为(2i+1)，其平方为4i^2+4i+1，平方的索引为(4i^2+4i+1-1)/2 = 2i^2+2i = 2i(i+1)；从这里开始，我们按值增加2(2i+1)，即在索引中增加(2i+1)。参见c++代码。 - Will Ness

@WillNess 看起来这是一个很大的改进！我会仔细研究一下。非常感谢！你似乎是这方面的专家之一！ - hiro protagonist

@hiroprotagonist 谢谢。其实我并不是很懂，只是曾经回答过很多简单的问题。我从来没有涉及过复杂的东西。 - Will Ness

@hiroprotagonist 对于“专家级”的内容，请参见例如 https://codegolf.stackexchange.com/questions/74269/calculate-the-number-of-primes-up-to-n/ :) - Will Ness