使用筛选法查找质数时代码报错，请求问题排查帮助

我尝试用「移除列表中质数倍数」的方法查找质数，但运行代码时触发了类型错误，原代码和报错信息如下：

原代码 #

def first_prime_fn(first,last):
    for x in range (first,last):
        for y in range (2,x):
            if x % y == 0:
                break
        else:
            prime = x
            return prime

def remove_multiple(num, lst):
    for n in range(2, len(lst)):
        if n * num in lst:
            lst.remove(num * n)
    return lst


def prime_finder(start,end):
    prime_list = [x for x in range (start, end+1)]
    for n in range(start,end):
        prime = first_prime_fn(n, end)
        remove_multiple(prime,prime_list)
    print(prime_list)

prime_finder(4,100)

报错信息 #

Traceback (most recent call last):
   File "script.py", line 24, in <module>
     prime_finder(4,100)
   File "script.py", line 21, in prime_finder
     remove_multiple(prime,prime_list)
   File "script.py", line 12, in remove_multiple
     if n * num in lst: TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

问题根源 #

1. first_prime_fn返回None：当传入的first到last范围内没有质数时，函数没有明确返回值，默认返回None。比如循环到n=99时，first_prime_fn(99,100)检查99（不是质数），没有进入else分支，最终返回None。此时remove_multiple接收的num是None，执行n * num就会触发类型错误。
2. remove_multiple循环逻辑混乱：
   • 循环范围用range(2, len(lst))完全不合理，应该计算num的倍数上限（即end // num），超过这个值的倍数根本不在列表里。
   • 直接遍历列表并调用remove会导致列表长度动态变化，后续元素被跳过（比如移除一个元素后，下一个元素前移，但循环索引仍递增），导致漏删。
3. prime_finder循环冗余：不需要从start到end逐个循环找质数，只要找到当前列表里的第一个质数，移除其倍数后，继续找下一个质数，直到质数的平方超过end（这是埃氏筛的核心逻辑，能大幅减少无效操作）。

修复后的代码 #

def first_prime_fn(first, last):
    # 确保从2开始，小于2的数没有质数
    for x in range(max(first, 2), last + 1):
        # 质数判断优化：只需检查到x的平方根，减少循环次数
        is_prime = True
        for y in range(2, int(x**0.5) + 1):
            if x % y == 0:
                is_prime = False
                break
        if is_prime:
            return x
    return None  # 明确返回None，避免隐式返回

def remove_multiple(num, lst, end):
    # 生成所有需要移除的倍数（从2倍开始，保留质数本身）
    max_multiple = end // num
    multiples = [num * n for n in range(2, max_multiple + 1)]
    # 用列表推导式生成新列表，避免原列表修改导致的遍历问题
    return [x for x in lst if x not in multiples]

def prime_finder(start, end):
    # 过滤小于2的数，同时生成初始列表
    prime_list = [x for x in range(max(start, 2), end + 1)]
    
    while True:
        # 找到当前列表范围内的第一个质数
        current_prime = first_prime_fn(2, end)
        # 如果没有质数，或质数平方超过上限，停止循环
        if current_prime is None or current_prime ** 2 > end:
            break
        # 移除当前质数的所有倍数
        prime_list = remove_multiple(current_prime, prime_list, end)
        # 移除已处理的质数，避免重复处理
        if current_prime in prime_list:
            prime_list.remove(current_prime)
        # 重新加入当前质数（因为remove_multiple不会删除它本身）
        prime_list.insert(0, current_prime)
    
    # 最后过滤一遍，确保列表里只剩质数
    final_primes = []
    for num in prime_list:
        is_p = True
        for y in range(2, int(num**0.5)+1):
            if num % y ==0:
                is_p = False
                break
        if is_p:
            final_primes.append(num)
    print(final_primes)

prime_finder(4,100)

优化点说明 #

• 质数判断优化：将内层循环的上限改为目标数的平方根，大幅减少循环次数。
• 移除倍数时使用列表推导式生成新列表，彻底避免原列表动态修改导致的遍历错误。
• 循环逻辑调整为标准埃氏筛流程，减少无效循环，提升效率。

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