Python3使用平方根质数判定法时出现超时问题求助

我来帮你完成这个严格遵循指定规则的质数判定程序～核心思路就是仅用小于目标数平方根的质数来试除，而且生成质数列表的时候也完全套用这个逻辑，下面是完整代码和细节解释：

import math

def generate_primes_up_to(limit):
    """生成所有小于等于limit的质数，生成过程仅用小于候选数平方根的质数试除"""
    if limit < 2:
        return []
    primes = [2]
    # 从3开始遍历奇数，跳过偶数提升效率
    for candidate in range(3, limit + 1, 2):
        # 计算候选数的平方根，取整后加1确保覆盖边界
        sqrt_candidate = int(math.sqrt(candidate)) + 1
        # 用已生成的、小于等于候选数平方根的质数来试除
        is_prime = True
        for p in primes:
            if p > sqrt_candidate:
                break
            if candidate % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(candidate)
    return primes

def is_prime(n):
    """判断n是否为质数，仅用小于其平方根的质数试除"""
    # 处理边界情况
    if n <= 1:
        return False
    if n == 2:
        return True
    # 大于2的偶数直接排除
    if n % 2 == 0:
        return False
    
    # 计算n的平方根上限，生成所有小于等于该值的质数
    sqrt_n = int(math.sqrt(n)) + 1
    primes_to_check = generate_primes_up_to(sqrt_n)
    
    # 用这些质数试除n
    for p in primes_to_check:
        if n % p == 0:
            return False
    return True

代码逻辑说明 #

• 边界处理：先快速排除小于等于1的数、大于2的偶数，减少不必要的计算
• 质数生成函数：generate_primes_up_to从最小的质数2开始，逐个检查奇数候选数。对每个候选数，只使用已经生成的、小于等于其平方根的质数来试除，完全符合你要求的规则
• 质数判定逻辑：对目标数n，先算出它的平方根上限，生成所有小于等于该上限的质数，再用这些质数逐个试除n——只要能被其中一个整除，就不是质数；反之则是质数

测试示例 #

比如你提到的数字33：

• sqrt(33)≈5.74，所以生成的质数列表是[2,3,5]
• 33 ÷ 3 = 11，能被整除，所以is_prime(33)返回False，结果正确

再测试质数37：

• sqrt(37)≈6.08，生成的质数列表还是[2,3,5]
• 37无法被这三个数整除，所以is_prime(37)返回True，结果正确

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