了解Python中的Eratosthenes筛

Question

我在python中找到了一个示例代码，该示例代码给出了所有素数，n但是我根本不明白，为什么这样做呢？

我已经阅读了有关Eratosthenes筛网的Wikipedia文章，但对它的工作原理一无所知。

pp = 2

ps = [pp]

lim = raw_input("Generate prime numbers up to what number? : ")

while pp < int(lim):

    pp += 1

    for a in ps:

        if pp%a==0:

            break

        else:

            ps.append(pp)

print set(ps)

对循环如何工作的解释将不胜感激。

Answer 1

该代码是尝试使用试除法生成素数序列的尝试。要更正它：pp = 2ps = [pp]lim = raw_input("Generate prime numbers up to what number? : ")while pp < int(lim):&nbsp; &nbsp; pp += 1&nbsp; &nbsp; for a in ps:&nbsp; &nbsp; &nbsp; &nbsp; if pp%a==0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # unindent&nbsp; &nbsp; &nbsp; &nbsp; ps.append(pp)&nbsp; &nbsp; #&nbsp; this为了使其更加有效（实际上是最佳）试验划分，请执行以下操作：pp = 2ps = [pp]lim = raw_input("Generate prime numbers up to what number? : ")while pp < int(lim):&nbsp; &nbsp; pp += 1&nbsp; &nbsp; for a in ps:&nbsp; &nbsp; &nbsp; &nbsp; if a*a > pp:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# stop&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ps.append(pp)&nbsp; &nbsp; #&nbsp; early&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; if pp%a==0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break

Answer 2

首先，这不是一个筛子。这就是它的工作方式。 pp是我们要测试的数字。在while循环的每次迭代中，我们遍历所有已知的质数（ps）并检查它们是否相除pp。如果其中有一个pp不是质数，我们将移至下一个数字。否则，我们在pp继续之前将其添加到素数列表中。这行pp%a==0基本上说的是“pp除以a零时的余数”，即a除pp而pp不是素数。一直持续到我们检查的数字大于我们设置的上限（lim）[编辑：这是一个筛子]isPrime = [True for i in range(lim)]isPrime[0] = FalseisPrime[1] = Falsefor i in range(lim):&nbsp; &nbsp; if isPrime[i]:&nbsp; &nbsp; &nbsp; &nbsp; for n in range(2*i, lim, i):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; isPrime[n] = False这不是最有效的筛子（效率更高的筛子可以执行for n in range(2*i, lim, i):生产线中的工作，但是它是有效的，并且isPrime[i]如果i是首要的，那将是正确的）。