python - Eratosthenes 筛法 - X 和 N 之间的素数

Question

我在 Stack Overflow 上发现了这个针对 Python 的埃拉托色尼筛法的高度优化实现。我大概知道它在做什么，但我必须承认它的工作细节让我难以理解。

我仍然想将它用于一个小项目(我知道有库可以做到这一点，但我想使用这个功能)。

原文如下:

'''
    Sieve of Eratosthenes 
    Implementation by Robert William Hanks      
    https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188
'''

def sieve(n):
    """Return an array of the primes below n."""
    prime = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool)
    for i in range(3, int(n**.5) + 1, 3):
        if prime[i // 3]:
            p = (i + 1) | 1
            prime[       p*p//3     ::2*p] = False
            prime[p*(p-2*(i&1)+4)//3::2*p] = False
    result = (3 * prime.nonzero()[0] + 1) | 1
    result[0] = 3
    return numpy.r_[2,result]

我想要实现的是修改它以返回 n starting at x 下的所有质数，以便:

primes = sieve(50, 100)

将返回 50 到 100 之间的质数。这似乎很简单，我尝试替换这两行:

def sieve(x, n):
    ...
    for i in range(x, int(n**.5) + 1, 3):
    ...

但是由于我无法解释的原因，上面的x的值对返回的numpy数组没有影响!

我如何修改 sieve() 以仅返回 x 和 n 之间的素数>/强>

Answer 1

您借用的实现能够从 3 开始，因为它通过跳过所有偶数代替筛选出 2 的倍数；这就是2*…在代码中多次出现的是关于。 3 是下一个质数这一事实也在各处进行了硬编码，但我们暂时忽略它，因为如果你无法通过 2 的特殊情况，那么 3 的特殊情况就无关紧要了.

跳过偶数是“轮子”的特例。您可以通过始终递增 2 来跳过筛选 2 的倍数；您可以通过交替递增 2 和 4 来跳过筛选 2 和 3 的倍数；您可以通过交替递增 2、4、2、4、6、2、6……(序列中有 48 个数字)等来跳过 2、3、5 和 7 的倍数筛选。因此，您可以扩展此代码，方法是首先找到所有不超过 x 的素数。 ，然后构建一个轮子，然后使用该轮子找到 x 之间的所有素数和 n .

但这增加了很多复杂性。一旦超过 7 个，成本(时间和存储车轮的空间)就会抵消节省的成本。如果你的整个目标不是找到 x 之前的素数, 找到 x 之前的素数所以你不必找到它们似乎有点傻。 :)

更简单的做法是找出所有不超过 n 的素数, 并扔掉下面的 x .你可以在最后做一个微不足道的改变:

primes = numpy.r_[2,result]
return primes[primes>=x]

或者当然有一些方法可以做到这一点，而不会为您要丢弃的那些初始素数浪费存储空间。将它们用于此算法会有点复杂(您可能希望分段构建数组，然后删除每个完全是 < x 的部分，然后堆叠所有剩余部分)；使用并非为空间上的速度和简单性而设计的算法的不同实现要容易得多……

当然还有不同的素数查找算法，它们不需要枚举所有素数直到x。首先。但是如果你想使用这个算法的这个实现，那没关系。