一尘不染

Eratosthenes筛-X和N之间的质数

algorithm

我在堆栈溢出中找到了针对Python的Eratosthenes筛的高度优化的实现。我对它的功能有一个大概的了解,但是我必须承认它的运作细节让我难以理解。

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

这是原始的:

'''
    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 以下 开始的 所有素数 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


阅读 321

收藏
2020-07-28

共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。但是,如果要使用此算法的此实现,则没关系。

2020-07-28