使用sqrt和ceil实现埃拉托斯特尼筛法的Python脚本问题求助

没问题，我来帮你搞定这个符合要求的埃拉托斯特尼筛法脚本！咱们一步步来实现，确保满足所有指定要求：

首先明确所有硬性要求：

• 必须使用math.sqrt()和math.ceil()函数
• 正确返回指定测试用例的质数列表
• 输入非正整数时抛出ValueError

完整代码实现 #

import math

def sieve(n):
    # 处理非正输入的异常逻辑
    if n < 2:
        raise ValueError("输入必须是大于等于2的整数")
    
    # 初始化筛子：索引对应数字，值标记是否为质数
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0和1明确不是质数
    
    # 计算循环上限：用平方根+向上取整，确保覆盖所有可能的因子
    max_factor = math.ceil(math.sqrt(n))
    
    for i in range(2, max_factor + 1):
        if is_prime[i]:
            # 从i的平方开始标记倍数（更小的倍数已被之前的质数处理过）
            for multiple in range(i*i, n+1, i):
                is_prime[multiple] = False
    
    # 收集所有标记为质数的数字
    return [num for num, prime in enumerate(is_prime) if prime]

代码细节解释 #

1. 输入验证：

   • 首先判断输入n是否小于2，直接抛出ValueError，完美处理sieve(0)和sieve(-4)的异常测试要求。

2. 筛子初始化：

   • 创建长度为n+1的布尔列表，索引对应0到n的数字，初始全设为True，再手动把0和1标记为False（它们不属于质数范畴）。

3. 循环上限计算：

   • 用math.sqrt(n)获取n的平方根，再通过math.ceil()向上取整得到max_factor。这样做的逻辑是：一个数若存在大于其平方根的因子，对应的另一个因子必然小于平方根，因此只需检查到平方根上限即可。用ceil能确保即使平方根是小数，也能覆盖到最接近的整数（比如n=5时，sqrt(5)≈2.236，ceil后是3，但此时3*3=9>5，内层循环不会执行，完全不影响结果）。

4. 标记非质数：

   • 遍历2到max_factor的每个数i，若i是质数（is_prime[i]为True），就从i*i开始，以i为步长标记所有倍数为非质数。从i*i开始是因为更小的倍数已经被之前的质数标记过，能提升效率。

5. 结果收集：

   • 用列表推导式遍历筛子列表，收集所有标记为True的索引，就是2到n之间的所有质数。

测试验证 #

咱们跑一遍要求的测试用例，确保全部通过：

# 正常功能测试
assert sieve(2) == [2]
assert sieve(3) == [2, 3]
assert sieve(4) == [2, 3]
assert sieve(5) == [2, 3, 5]

# 异常场景测试
try:
    sieve(0)
except ValueError:
    print("sieve(0) 正确抛出ValueError")
else:
    assert False, "sieve(0) 未抛出ValueError"

try:
    sieve(-4)
except ValueError:
    print("sieve(-4) 正确抛出ValueError")
else:
    assert False, "sieve(-4) 未抛出ValueError"

所有测试都会顺利通过，完全满足你的需求！

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