python - 使用 boolean 值列表进行埃拉托色尼筛选

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)

它确实打印了一个列表，但我被告知我做错了。有人告诉我需要传递一个 boolean 值列表，并返回一个素数列表。逻辑是我从长度为 N 的输入中创建一个 boolean 值列表。我想出了如何用这个创建一个 boolean 值列表

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

如果我使用打印，它会给我这个。

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

我需要能够将前两个值 true 转为 false，然后将第三个“true”的值保留为 true，但将 2 的所有倍数转为 false，然后对 3、5 执行相同的逻辑， 7 等等，直到我把 list 列出来。然后我需要能够以某种方式扫描它以查找剩余的真实值，并打印这些数字的列表作为我的质数。我真的迷失了，因为我不知道如何将“True”列表的值更改为 false，以及如何在循环中执行此操作以及如何知道何时停止。任何帮助将不胜感激。

Answer 1

噢，伙计，优质筛子!这就是我学习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 大于列表中最大数字的平方根时，你就停止。每个仍标记为素数的数字都是素数!

在构建列表和筛选时可以跳过偶数，但这有点复杂。