了解Python中的Eratosthenes筛

Question

我在python中找到了一个示例代码，该示例代码给出了所有素数，n但是我根本不明白，为什么这样做呢？我已经阅读了有关Eratosthenes筛网的Wikipedia文章，但对它的工作原理一无所知。pp = 2ps = [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 = 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:                # unindent

        ps.append(pp)    #  this

为了使其更加有效（实际上是最佳）试验划分，请执行以下操作：

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 a*a > pp:         # stop

            ps.append(pp)    #  early

            break

        if pp%a==0:

            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] = False

isPrime[1] = False

for i in range(lim):

    if isPrime[i]:

        for n in range(2*i, lim, i):

            isPrime[n] = False

这不是最有效的筛子（效率更高的筛子可以执行for n in range(2*i, lim, i):生产线中的工作，但是它是有效的，并且isPrime[i]如果i是首要的，那将是正确的）。