如何用Python实现埃拉托斯特尼筛法双功能并修复prime未引用报错

核心错误原因 #

• prime未引用报错的直接原因：在sieve函数内调用label(prime, n)时，prime变量未在当前作用域定义，传入不存在的变量触发引用错误
• label函数的入参设计冗余：调整后的label内部已经完成了标记数组的初始化，不需要额外接收prime作为入参
• 原sieve逻辑错误：循环内遇到第一个素数就直接返回，仅能返回单个结果，无法收集所有符合要求的素数

正确拆分实现 #

两个函数的职责划分保持要求：label负责完成素数/非素数的标记，sieve负责基于标记结果返回素数列表，实现代码如下：

def label(n):
    # 初始化布尔数组，下标对应数字，值为True代表对应下标是素数
    prime = [True for _ in range(n + 1)]
    # 0和1不属于素数，直接标记为False
    prime[0], prime[1] = False, False
    # 埃氏筛核心逻辑：遍历到根号n即可完成所有合数的标记
    for i in range(2, int(n ** 0.5) + 1):
        # 仅当i本身是素数时，标记其倍数，减少冗余操作
        if prime[i]:
            for j in range(2 * i, n + 1, i):
                prime[j] = False
    return prime

def sieve(n):
    # 调用label函数获取标记完成的数组
    marked_arr = label(n)
    # 收集所有标记为True的下标，即为小于等于n的素数
    prime_list = [num for num in range(n + 1) if marked_arr[num]]
    return prime_list

可通过以下方式测试效果：

# 输出小于等于20的所有素数
print(sieve(20))
# 预期输出：[2, 3, 5, 7, 11, 13, 17, 19]

内容的提问来源于stack exchange，提问作者Max-ine-93