python - 有人可以帮我理解这个Eratosthenes筛网脚本吗？最后几行让我难过

好吧，所以我得到了Eratosthenes筛网背后的原理。我尝试自己写一个，但在很大程度上失败了（我写了一个功能性质数生成器，它效率不高，也不是一个筛子）。我想我在理解数学上还有更多的问题，但是编程也让我感到困惑。import numpy as npdef primesfrom2to(n): sieve = np.ones(n/3 + (n%6==2), dtype=np.bool) # print(sieve) for n = 10 returns [True, True, True]好吧，撇开蝙蝠，我有点困惑。它会生成一个真值列表，这些真值将在确定为复合值时逐渐标记为false。我认为这是在小于n的值中，不超过1/3的将是质数，但是添加模态运算能实现什么呢？ sieve[0] = False标记1为假？ 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]是true（所以质数/尚未标记为复合？），那么3*i + 1 or 1？究竟如何运作？似乎产生质数，以后会乘以删除所有后续乘积，但我不知道如何。 sieve[ ((k*k)/3) ::2*k] = False sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False好的，所以这两个都取质数k并标记了它们的所有其他倍数吗？如果n=5不能使它成为sieve[8.33::10] = False？而另一个像sieve[41.3::10]一样？我就是不明白。print(np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)])好的，最后实际上生成了素数列表。同样，将其乘以三又是怎么回事？显然，这段代码中有3个基本知识，我是无法理解的。同样，我也无法再次理解|1概念。哦，只是为了好玩，这是我有效而可怕的低效率尝试。import numpydef 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)计算素数高达500,000用了57秒。我当时在做欧拉素数至2,000,000的问题。 最佳答案 这是numpy中的一种简单筛子算法：import numpy as npdef 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)如果删除了打印语句，则在我适中的笔记本电脑上它会在2.5秒内运行Nmax = 10 ^ 8。该算法效率不高，因为它需要存储偶数值和3的倍数的素数。您可以通过过滤掉那些值来节省存储空间，以便跟踪n * 6 + 1的素数。 n * 6 + 5，对于任何整数n> = 1。这样可以节省三分之二的存储空间，但要多花一些记帐本。看来您尝试从困难版本开始。而且，如果涉及到Python解释器评估if语句并执行列表的内存管理，那么所有簿记都将变得昂贵。 Python / numpy的数组切片是一种更自然的方法，它可能足够快达到您的目的。关于您的问题：（n％6 == 2）为布尔值，将被解释为0或1，并将再添加一个元素以防止出现“ by-by-one”错误。int(n**0.5)//3+1应该读为int(int(n**0.5)/3) + 1。除法之前先除法。除以3是为了只分配6n + 1和6n + 5值的空间。k=3*i+1|1表示k=3*i+1，如果是偶数，则加一个（按位或）。数组元素“ i”对应于潜在素数(3*i+1)|1。因此，如果数组索引为[0, 1, 2, 3, 4, 5, ...]，则它们表示数字[1, 5, 7, 11, 13, 17, ...]。对于表示6n + 1和6n + 5的元素，分别将sieve元素设置为False，这就是为什么要进行两次分配的原因。如果您在Python 2.7中运行此命令，整数除法将始终被截断，因此9/2将得到4。在Python 3中，最好对整数除法使用//运算符，即(k*k)/3应该为。编辑：您可能希望归因于您所询问的算法：Fastest way to list all primes below N。