使用布尔列表的Eratosthenes的筛子

Question

好的我正在尝试制作Eratosthenes的筛子。我最初使用这个代码。

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] 

我需要能够真正的前两个值变成假的，然后离开第三个“真”是真正的价值，但把两个假倍数，然后做同样的逻辑3，5,7等，直到我耗尽名单。然后，我需要能够以某种方式扫描剩余的真值，并将这些数字列表作为我的素数打印出来。我真的迷失了，因为我不知道如何将“真”列表的值更改为假，以及如何在循环中做到这一点，以及如何知道何时停止。任何帮助，将不胜感激。

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大于列表中最大数字的平方根时，你停止。每一个仍然被标记为素数的数字是素数！

当你建立你的列表和筛选时，可以跳过偶数，但这有点复杂。

Answer 2

我写了一个函数用于Project Euler问题，这个问题可能比Broseph的解决方案稍微清晰一些，并随着它的发展积累素数（如果您使用python3更改xrange - >范围）。

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