相关疑难解决方法(0)

这是我能提出的最佳算法.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

可以做得更快吗？

此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

我在 NumPy 中实现了自己的埃拉托斯特尼筛法。我相信你们都知道它是为了找到一个数字以下的所有素数，所以我不会进一步解释。

代码：

import numpy as np\n\ndef primes_sieve(n):\n    primes = np.ones(n+1, dtype=bool)\n    primes[:2] = False\n    primes[4::2] = False\n    for i in range(3, int(n**0.5)+1, 2):\n        if primes[i]:\n            primes[i*i::i] = False\n\n    return np.where(primes)[0]\n

正如你所看到的，我已经做了一些优化，首先除了 2 之外所有素数都是奇数，所以我将 2 的所有倍数设置为False且仅是暴力奇数。

其次，我只循环遍历直到平方根下限的数字，因为平方根之后的所有合数都会因平方根以下素数的倍数而被消除。

但这不是最佳的，因为它循环遍历低于限制的所有奇数，并且并非所有奇数都是质数。随着数字的增大，素数变得更加稀疏，因此存在大量冗余迭代。

因此，如果候选列表是动态更改的，以这样的方式，已经识别的合数甚至不会被迭代，因此只有质数被循环，不会有任何浪费的迭代，因此算法将是最优的。

我写了一个优化版本的粗略实现：

def primes_sieve_opt(n):\n    primes = np.ones(n+1, dtype=bool)\n    primes[:2] = False\n    primes[4::2] = False\n    limit = int(n**0.5)+1\n    i = 2\n    while i < limit:\n        primes[i*i::i] = False\n        i += 1 + …