维基百科的埃拉托色尼筛子算法伪代码的实现

Question

尝试实现埃拉托色尼素数算法筛的维基百科伪代码版本。

伪代码:

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的整数。我一直在挠头，为什么它不工作-尝试了各种缩进结构，没有运气。

编辑:执行@trincot的建议，似乎有效。欢迎对代码改进提出任何建议!

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

Answer 1

您没有按照维基百科上的说明实现它。

1. 您没有指定False，但是将与False进行了比较。应该是单个=

2. print发生在外循环的每次迭代中。这在两个方面是错误的:

   • 只有当列表值为True
   时才应该打印
   • 它应该在一个单独的循环中完成，因为当前的外部循环只上升到n的平方根，而您需要检查整个列表。

如果您进行这些更正，它将与所描述的算法对齐。正确的Python实现可以在这个站点的其他地方找到，比如这里。

Answer 2

changein_list[j] == Falsetoin_list[j] = False

import math
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  
for i, is_prime in enumerate(in_list):
if is_prime:
print(i)
createListOfPrimes()

Answer 3

import math
def createListOfPrimes():
n = int(input("Enter an integer n>1:  "))
in_list = [True for i in range(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    

return in_list

primes = createListOfPrimes()

== False是错误的，调用print函数没有任何意义，只是返回一个列表。此外，您可以编写更好的代码，例如，对布尔列表使用列表推导式。