Python实现维基版埃拉托斯特尼筛法伪代码的排错与优化

本人尝试实现公开资料中给出的埃拉托斯特尼素数筛（Sieve of Eratosthenes）算法伪代码版本。

算法参考伪代码 #

algorithm Sieve of Eratosthenes is
    input: an integer 𝑛 > 1.
    output: all prime numbers from 2 through 𝑛.

    let 𝐴 be an array of Boolean values, indexed by integers 2 to 𝑛,
    initially all set to true.
    
    for 𝑖 = 2, 3, 4, ..., not exceeding √𝑛 do
        if 𝐴[𝑖] is true
            for 𝑗 = 𝑖², 𝑖²+𝑖, 𝑖²+2𝑖, 𝑖²+3𝑖, ..., not exceeding 𝑛 do
                set 𝐴[𝑗] := false

    return all 𝑖 such that 𝐴[𝑖] is true.

初始问题代码 #

def createListOfPrimes():
  n = int(input("Enter an integer n>1:  "))
  in_list = [True]*(n+1)
  for i in range(2, int(math.sqrt(n)+1)):
    if in_list[i] == True:
      for j in range(i**2, n+1, i):
        in_list[j] == False    
    print(i)

故障现象 #

输入n=90调用createListOfPrimes()时，函数仅输出2到9区间内的整数，多次调整代码缩进结构均未解决问题。

故障原因 #

代码存在两处核心逻辑错误：

• 合数标记语句无效：内层筛数循环中写的in_list[j] == False是布尔比较操作，不是赋值操作，执行时只会返回True/False的判断结果，根本不会修改数组里的标记值，整个筛除合数的逻辑完全没有生效。
• 结果输出逻辑完全错误：print(i)被放在了外层遍历循环内部，这个循环的i取值上限是√n（n=90时√n≈9.49，i最大取值为9），自然只会打印2到9的数。按照算法逻辑，必须等所有筛除操作完成后，再遍历整个标记数组，收集所有值为True的下标，才是最终的素数列表。

修正后可运行代码 #

采纳建议修改后代码已可正常运行，欢迎提供进一步的代码优化方向：

def createListOfPrimes():
  n = int(input("Enter an integer n>1:  "))
  in_list = [True]*(n+1)
  prime_list = []
  for i in range(2, int(math.sqrt(n)+1)):
    if in_list[i] == True:
      for j in range(i**2, n+1, i):
        in_list[j] = False    
  for i in range(2,n+1):
    if in_list[i]==True:
      prime_list.append(i)
  return prime_list

内容的提问来源于stack exchange，提问作者coding girl