无2倍和3倍的埃拉托斯特尼筛

Question

我正在尝试实现本文Faster Sieve of Eratosthenes中描述的算法。我很理解这个想法，但我无法理解如何通过python代码实现它。

经过一些工作，我找到了一种将索引从筛子转换为数字本身的方法：

number=lambda i:3*（i 2）-1-（ii）%2

但主要问题是我在获得总理后必须做的跳跃。文章将其解释为：

6np±p，其中p是素数，n是一些自然数。

对于这样一个想法，有没有办法用最后发现的质数的指数来描述跳跃？

提前致谢。

附言。Objective-C中有实现，我对编程很陌生，只能理解python和js代码。

Answer 1

如果您了解numpy和Python，请看primesfrom2to的实现，它取自StackOverflow中的答案。

def primesfrom2to(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = np.ones(n/3 + (n%6==2), dtype=np.bool)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      ((k*k)/3)      ::2*k] = False
            sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False
    return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]

在我链接的那个答案中，这个例程是构建素数列表中最快的。我在自己的探索素数的代码中使用了它的变体。详细解释这一点需要很多空间，但它构建了一个筛子，省去了2和3的倍数。只需两行代码（以sieve[开始，以=False结束）就可以标记出一个新发现的素数的倍数。我想这就是你所说的“获得素数后跳转……”的意思。这段代码很棘手，但需要努力学习。这段码是为Python 2编写的，即传统的Python。

以下是我自己的一些Python 3代码，其中包含更多注释。您可以使用它来进行比较。

def primesieve3rd(n):
    """Return 'a third of a prime sieve' for values less than n that
    are in the form 6k-1 or 6k+1.

    RETURN: A numpy boolean array. A True value means the associated
            number is prime; False means 1 or composite.

    NOTES:  1.  If j is in that form then the index for its primality
                test is j // 3.
            2.  The numbers 2 and 3 are not handled in the sieve.
            3.  This code is based on primesfrom2to in
                <https://stackoverflow.com/questions/2068372/
                fastest-way-to-list-all-primes-below-n-in-python/
                3035188#3035188>
    """
    if n <= 1:  # values returning an empty array
        return np.ones(0, dtype=np.bool_)
    sieve = np.ones(n // 3 + (n % 6 == 2), dtype=np.bool_)  # all True
    sieve[0] = False   # note 1 is not prime
    for i in range(1, (math.ceil(math.sqrt(n)) + 1) // 3): # sometimes large
        if sieve[i]:
            k = 3 * i + 1 | 1  # the associated number for this cell
            # Mark some of the stored multiples of the number as composite
            sieve[k * k                 // 3 :: 2 * k] = False
            # Mark the remaining stored multiples (k times next possible prime)
            sieve[k * (k + 4 - 2*(i&1)) // 3 :: 2 * k] = False
    return sieve

def primesfrom2to(n, sieve=None):
    """Return an array of prime numbers less than n.

    RETURN: A numpty int64 (indices type) array.

    NOTES:  1.  This code is based on primesfrom2to in
                <https://stackoverflow.com/questions/2068372/
                fastest-way-to-list-all-primes-below-n-in-python/
                3035188#3035188>
    """
    if n <= 5:
        return np.array([2, 3], dtype=np.intp)[:max(n - 2, 0)]
    if sieve is None:
        sieve = primesieve3rd(n)
    elif n >= 3 * len(sieve) + 1 | 1:  # the next number to note in the sieve
        raise ValueError('Number out of range of the sieve in '
                         'primesfrom2to')
    return np.r_[2, 3, 3 * np.nonzero(sieve)[0] + 1 | 1]

问我这里是否有你不明白的事情。