有人能帮我理解这个埃拉托色尼筛子的剧本吗？最后几行让我困惑

Question

好了，我明白了厄拉多塞筛子背后的原理。我试着自己写一个，但基本上失败了(我写了一个函数式的素数生成器，它不是很有效，也不是一个筛子)。我想我在理解数学上更有问题，但是编程也把我搞糊涂了。

import numpy as np

def primesfrom2to(n):
    sieve = np.ones(n/3 + (n%6==2), dtype=np.bool) 
    # print(sieve) for n = 10 returns [True, True, True] 

好了，把球棒注销我有点糊涂了。它正在生成一个真值列表，当它们被确定为复合值时，将逐渐被标记为假。我认为它是说不超过1/3的小于n的值是质数，但是增加一个modolus运算能得到什么呢？

    sieve[0] = False

将1标记为false？

    for i in range(int(n**0.5)//3+1):
        # print(i) for n = 10 returns 0 and 1 on separate lines

这是要检查的范围设置。没有一个数字的乘积大于其平方根。除以3 1是怎么回事？

        if sieve[i]:
            k=3*i+1|1
            #print(k) for n = 10 returns '5' doesn't change till it adds 7 at n = 50

好的，那么，如果sieve[i]为真（所以素数/尚未标记为复合？）那么3*i 1或1？这到底是如何工作的？它似乎正在生成素数，稍后将乘以删除所有后续产品，但我不知道如何操作。

            sieve[      ((k*k)/3)      ::2*k] = False
            sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False

好的，这两个都是取素数k并标记它们的所有进一步倍数？如果n=5，这不会导致筛分[8.33:：10]=False吗？另一个像筛子[41.3:：10]？我就是不明白。

print(np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)])

好的，最后实际生成素数列表。再问一次，乘以3是怎么回事？显然，这段html" target="_blank">代码中有一些关于3的基本内容我不明白。同样，我也没有理解< code>|1的概念。

哦，只是为了好玩，这是我有效且非常低效的尝试。

import numpy
def sieve(num):

    master = numpy.array([i for i in range(2, num+1)])
    run = []
    y=2


    while y <= ((num+1)**(1/2)): 
        thing = [x for x in range(y, num+1, y) if x > 5 or x == 4]
        run = run + thing
        y = y+1 
    alist = numpy.in1d(master, run, invert = True)
    blist = (master[alist])
    print(blist)

计算500000个素数需要57秒。我正在做2000000个素数的欧拉求和问题。

Answer 1

这是numpy中的一个简单筛选算法：

import numpy as np
def sieve(Nmax):
    """Calculate prime numbers between 0 and Nmax-1."""
    is_prime = np.ones(Nmax, dtype=bool)
    Pmax = int(np.sqrt(Nmax)+1)
    is_prime[0] = is_prime[1] = False
    p = 2
    dp = 1
    while p <= Pmax:
        if is_prime[p]:
            is_prime[p*2::p] = False
        p += dp
        dp = 2
    primes = np.argwhere(is_prime)[:,0]
    print(primes)

sieve(100)    

如果我删除print语句，它将在我的普通笔记本电脑上以2.5秒的速度运行Nmax=10^8。

此算法的效率有点低下，因为它需要存储偶数值的素数和 3 的倍数。您可以通过过滤掉这些来节省存储空间，以便跟踪任何整数n的n * 6 1和n * 6 5的素数

关于您的问题：

• （n%6==2）是布尔值，将被解释为0或1，并将添加一个元素以防止出现“off-by-one”错误。
• int（n**0.5）//3 1应读作int（int（n**0.5）/3）1。除法先于加法。除以3是为了只为6n 1和6n 5值分配空间。
• k=3*i1|1表示k=3*i 1（3*i 1）|1。因此，如果数组索引[0，1，2，3，4，5，…]，则它们表示数字[1，5，7，11，13，17，…]。
• 对于表示6n 1和6n 5的元素，分别将筛选元素设置为False，这就是为什么有两个赋值。
• 如果在Python 2.7中运行此命令，整数除法总是被截断，因此9/2将得到4。在Pythin 3中，最好使用//运算符来进行整数除法，即（k*k）/3应该是（k*k）//3

编辑：您可能希望归因于您询问的算法：列出N以下所有素数的最快方法。