python - 使用埃拉托斯特尼筛法给定范围内的素数

Question

我正在尝试打印小于“n”的素数。代码如下:

def prime_numbers(n):
    A=[1 for i in range(n+1)]
    for i in range(2,int(sqrt(n))):
        if A[i]==1:
            for j in range(i*2,n,i):
                A[j]=0
    for i in range(n):
        if A[i]:
            print(i)

输出

prime_numbers(10) 

是

0
1
2
3
5
7
9

程序正确打印 100。我需要进行哪些更改？

Answer 1

不包括range()中的终点。由于 sqrt(10) 为 3.1623，您的 range() 会循环到 2，不再循环，并且 3 的倍数不会从您的列表。您的代码适用于 100，因为您是否测试 10 的倍数并不重要(这些已经被 2 和 5 覆盖)。

同样的问题也适用于您的其他循环；如果您想将 n 本身包含为候选素数，您还应该将其包含在其他范围中。

请注意，您还想忽略 0 和 1，它们不是素数。您可以在顶部添加 A[0] = A[1] = False 以确保最后一个循环不包含这些内容，或者从 2 而不是 0 开始最后一个循环。

您想要在平方根上添加一个以确保它经过测试:

for i in range(2, int(sqrt(n)) + 1):

顺便说一句，为了清楚起见，我会使用 bool 值而不是 0 和 1(这里没有太大的性能或内存占用差异):

def prime_numbers(n):
    sieve = [True] * (n + 1)  # create a list n elements long
    for i in range(2, int(sqrt(n)) + 1):
        if sieve[i]:
            for j in range(i * 2, n + 1, i):
                sieve[j] = False
    for i in range(2, n + 1):
        if sieve[i]:
            print(i)

我使用 [..] * (n + 1) 创建了 n 项(加上 0)的列表；这会生成一个列表，其中包含左操作数内容的 n 个浅拷贝。这比列表理解更快，而且共享引用也很好，因为 True 是 Python 中的单例。

演示:

>>> prime_numbers(31)
2
3
5
7
11
13
17
19
23
29
31

请注意，其中包含 31；您的代码会导致不正确的输出，因为您会留下所有 5 的倍数。