使用埃拉托色尼筛法在给定范围内的素数

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)

是

程序正确打印 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):

我会使用布尔值而不是 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 的所有倍数。

使用埃拉托色尼筛法在给定范围内的素数

Prime numbers in a given range using Sieve of Eratosthenes

python

primes

python-3.x