埃拉托色尼筛 - X和N之间的素数 [英] Sieve of Eratosthenes - Primes between X and N

问题描述

我发现埃拉托色尼的筛的Python在code审查这种高度优化的实现。我有什么它做一个粗略的想法，但我必须承认，它的工作原理的细节逃避我。

I found this highly optimised implementation of the Sieve of Eratosthenes for Python on Code Review. I have a rough idea of what it's doing but I must admit the details of it's workings elude me.

我仍然想使用它的一个小项目（我知道有图书馆这样做，但我想用此功能）。

I would still like to use it for a little project (I'm aware there are libraries to do this but I would like to use this function).

下面是原文：

'''
    Sieve of Eratosthenes 
    Implementation by Gareth Rees       
    http://codereview.stackexchange.com/questions/42420/sieve-of-eratosthenes-python
'''

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质数这个的似乎的很容易，我试着更换两行：

would return primes between 50 and 100. This seemed easy enough, I tried replacing these two lines:

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

但对于原因，我无法解释，对 X 在上面的数值已经回到了numpy的阵列上没有影响力！

But for a reason I can't explain, the value of x in the above has no influence on the numpy array returned!

如何修改筛（）来的只有的的返回素数X 和 N

How can I modify sieve() to only return primes between x and n

推荐答案

您已经借来的实施能够开始3，因为它取代筛选出2的倍数，只需跳过所有偶数;这正是 2 * ... 多次出现在code是什么。事实上，3是下一任也很难codeD在所有的地方，但让我们忽略的时刻，因为如果你不能让过去的特殊外壳2，专用套管3没关系。

The implementation you've borrowed is able to start at 3 because it replaces sieving out the multiples of 2 by just skipping all even numbers; that's what the 2*… that appear multiple times in the code are about. The fact that 3 is the next prime is also hardcoded in all over the place, but let's ignore that for the moment, because if you can't get past the special-casing of 2, the special-casing of 3 doesn't matter.

跳过偶数是一种车轮的一种特殊情况。你可以跳过2筛分倍数由总是由2递增;可以跳过的2和3的倍数筛分由2和4交替地递增;可以跳过的2，3，5筛分倍数，和7由通过交替递增2，4，2，4，6，2,6，...（有序列中48号），等等。所以，你的可以的首先找出所有的素数高达扩展这个code X ，然后建立一个轮子，然后使用该轮之间找到所有质数X 和 N 。

Skipping even numbers is a special case of a "wheel". You can skip sieving multiples of 2 by always incrementing by 2; you can skip sieving multiples of 2 and 3 by alternately incrementing by 2 and 4; you can skip sieving multiples of 2, 3, 5, and 7 by alternately incrementing by 2, 4, 2, 4, 6, 2, 6, … (there's 48 numbers in the sequence), and so on. So, you could extend this code by first finding all the primes up to x, then building a wheel, then using that wheel to find all the primes between x and n.

但是，这增加了很多复杂性。一旦你太远远超出7，成本（包括时间，并在存储车轮空间）淹没储蓄。如果你的整个的目标不是要找到之前素数X ，找到以前素数X 让你不要找到他们，似乎有点傻。 ：）

But that's adding a lot of complexity. And once you get too far beyond 7, the cost (both in time, and in space for storing the wheel) swamps the savings. And if your whole goal is not to find the primes before x, finding the primes before x so you don't have to find them seems kind of silly. :)

最简单的方式做的就是找​​到所有素数高达 N ，并引发了那些低于 X 。你可以在其最后一个微不足道的变化做的：

The simpler thing to do is just find all the primes up to n, and throw out the ones below x. Which you can do with a trivial change at the end:

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

当然，还是有办法做到这一点不为你要扔掉那些最初的素数浪费存储。他们会有点复杂的工作，这个算法（你可能想打造的部分数组，然后删除每个节是完全＆LT; X ，当您去，那么栈中所有剩余的部分）;这将很容易来使用不同的实现，是不适合的速度和简易性上空间的算法...

Or course there are ways to do this without wasting storage for those initial primes you're going to throw away. They'd be a bit complicated to work into this algorithm (you'd probably want to build the array in sections, then drop each section that's entirely < x as you go, then stack all the remaining sections); it would be far easier to use a different implementation of the algorithm that isn't designed for speed and simplicity over space…

当然，还有的不同的的黄金发现算法不需要列举所有的素数高达 X 摆在首位。但是，如果你想用这个来实现这一算法的，这并不重要。

And of course there are different prime-finding algorithms that don't require enumerating all the primes up to x in the first place. But if you want to use this implementation of this algorithm, that doesn't matter.

这篇关于埃拉托色尼筛 - X和N之间的素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！