使用布尔列表的埃拉托斯特尼筛法

Question

好的，我正在尝试制作一个埃拉托斯特尼筛法。我最开始用的代码是这个。

def shake(n):
    n == 2                  # initializes 2 since it's first prime
    prime = []              # makes empty list
    for i in range(2, n+1): # takes range from 2 to N
        if i not in prime:  
            print (i)
            for i in range(i*i, n+1, i):
                prime.append(i)

shake(100)

这个代码确实能打印出一个列表，但有人告诉我我做错了。他们说我需要传入一个布尔值的列表，并返回一个质数的列表。逻辑是我从一个长度为N的输入中创建一个布尔值的列表。我找到了制作布尔值列表的方法，代码是这个。

def shake(alist)
    N = 10
    alist = [True for _ in range(N + 1)]

如果我用打印输出，它会给我这个结果。

[True True True True True True True True True True True]

我需要能够把前两个“真”的值改成“假”，然后把第三个“真”的值保持为“真”，但把所有2的倍数改成“假”，接着对3、5、7等做同样的处理，直到列表处理完为止。然后我需要能够扫描这个列表，找出剩下的“真”的值，并把这些数字打印出来作为我的质数。我真的很困惑，因为我不知道怎么把我的“真”的列表值改成“假”，也不知道怎么在循环中做到这一点，以及我该如何知道什么时候停止。任何帮助都非常感谢。

Answer 1

我写了一个函数，用来解决Project Euler的问题。这个函数可能比Broseph的解决方案更清晰，并且在运行时会逐步累积质数（如果你使用的是python3，把xrange改成range就可以了）。

primes(maxp):
    """
    Returns a list of all primes < maxp.
    """
    sieve = [True for x in xrange(maxp)]
    prime_lst = [1]
    for i in xrange(2, int(sqrt(maxp))):
        if sieve[i]:
            prime_lst.append(i)
            for j in xrange(2*i, maxp, i):
                sieve[j] = False
    return prime_lst

Answer 2

哎呀，质数筛选！这是我学习用Python编程的方式！这里有一个简单的例子：

def primes(n):
"""Finds all the primes less than n."""
    #First build your list of Trues
    ps = [1] * n
    #next, set the first two entries to False
    ps[0]=0; ps[1]=1
    #i is the index, p_i is the primality value.
    #the int(n**0.5) part makes us only look at the numbers less than the square
    #root of n.
    for i, p_i in enumerate(ps[:int(n**0.5)]):
        #if p_i is True then i is prime
        if p_i:
            #mark off every ith number from i^2 as nonprime
            for j in xrange(i*i, n, i):
                ps[j]=0
    #return every index that has the value True
    return [i for (i, p_i) in enumerate(ps) if p_i]

你有一个数字列表，所有的数字一开始都被标记为质数。你先取第一个数字n，然后从n的平方开始，标记每个第n个数字为非质数（也就是合成数）。当n大于列表中最大数字的平方根时，你就停止了。所有仍然被标记为质数的数字就是质数！

在你建立列表和筛选的时候，可以跳过偶数，但这样做会稍微复杂一些。