Eratosthenes的筛子 - X和N之间的Primes

Question

我在Stack Overflow上找到了针对Python的Eratosthenes Sieve的这种高度优化的实现.我对它正在做什么有一个粗略的想法,但我必须承认它的工作细节没有我.

我仍然希望将它用于一个小项目(我知道有些库可以做到这一点,但我想使用这个函数).

这是原始的:

'''
    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

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.但是如果你想使用这种算法的实现,那没关系.