了解 Python 中的埃拉托色尼筛法 [英] Understanding Sieve of Eratosthenes in Python

问题描述

我在 python 中找到了一个示例代码，它给出了 n 之前的所有质数，但我就是不明白，为什么它会这样做?

I've found an example code in python that gives out all prime numbers upto n but I simply don't get it, Why does it does what it does?

我已阅读有关 埃拉托色尼筛网 的维基百科文章，但根本不知道这是如何工作的.

I've read the wikipedia article about the Sieve of Eratosthenes but simply have no idea about how this works.

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)

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

An explanation of how the loop works would be appreciated.

编辑 - 发现代码全错了，因为它表示 25 作为素数，通过更深入的搜索发现这不是没有筛子，有人可以展示一个使用python中的筛子并解释它的生成器

推荐答案

该代码尝试使用试除法生成素数序列.

That code is an attempt at using trial division to produce a sequence of primes.

纠正它:

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

为了使其更有效(实际上是最佳的)试验划分:

To make it much more efficient (in fact, optimal) trial division:

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

这篇关于了解 Python 中的埃拉托色尼筛法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！