You need to enable JavaScript to run this app. 如何优化验证勒让德猜想的Python程序运行效率
优惠活动
大模型
产品
解决方案
定价
更多

如何优化验证勒让德猜想的Python程序运行效率

勒让德猜想验证代码的性能优化

原代码的性能瓶颈

  • 素数判断冗余度极高:对每个待校验的整数i,循环从2遍历到i-1完成素数判定,单个数的判断时间复杂度为O(n)。实际上如果一个数存在大于√i的因子,必然存在一个对应的小于√i的因子,根本不需要遍历到i-1。
  • 大量无意义的全量计数:验证勒让德猜想的核心是确认每个平方区间内至少存在1个素数,不需要统计区间内素数的总数量。只要遍历到第一个素数,就可以立刻结束当前区间的检查,原代码会把整个区间的所有数全部检查完才进入下一个区间,浪费了大量计算资源。
  • 重复校验成本高:每检查一个新的平方区间,都要从头跑一遍素数判断逻辑,完全没有复用前面已经得到的素数校验结果,重复计算量随输入x的增大快速上升。
  • 存在逻辑瑕疵:原代码会将整数1误判为素数——当i=1时,内层素数判断的循环范围range(2,1)为空,计数不会增加,会被触发素数判定逻辑。这个问题虽然碰巧不会影响最终验证结果,但不符合素数的数学定义。

优化实现思路

核心优化:用埃拉托斯特尼筛法(埃氏筛)预先生成素数表

输入参数为x时,需要校验的所有整数的最大边界是(x+1)²,可以一次性标记出从2到这个边界的所有整数的素数属性,后续所有素数判断直接查表即可。这一步可以把整体时间复杂度从原代码的O(n³)量级降到O(n log log n),是提速最明显的优化操作。

配套优化

  • 每个平方区间遍历的时候,只要找到第一个素数就立刻跳出循环,不再扫描区间内剩余的数
  • 只要发现某一个区间没有素数,直接返回False,不需要继续检查后续区间
  • 明确将0、1标记为非素数,修正原代码的判定瑕疵

优化后的可运行代码

def legendre(x):
    # 计算所有需要校验的整数的最大范围
    max_check_bound = (x + 1) ** 2
    # 初始化素数标记表,初始默认所有数都是素数
    is_prime = [True] * (max_check_bound + 1)
    is_prime[0], is_prime[1] = False, False  # 0和1不属于素数
    # 埃氏筛标记非素数
    for base in range(2, int(max_check_bound ** 0.5) + 1):
        if is_prime[base]:
            # 从base的平方开始,标记所有base的倍数为非素数
            for multiple in range(base * base, max_check_bound + 1, base):
                is_prime[multiple] = False
    
    # 逐个区间验证猜想
    for n in range(1, x + 1):
        interval_low = n ** 2
        interval_high = (n + 1) ** 2
        has_valid_prime = False
        for num in range(interval_low, interval_high + 1):
            if is_prime[num]:
                has_valid_prime = True
                break  # 找到第一个素数就提前结束当前区间的检查
        # 发现区间没有素数,直接返回结果,无需继续遍历
        if not has_valid_prime:
            return False
    return True

实际提速效果

当输入x=500时,原代码需要执行的循环次数超过千万级,优化后的代码埃氏筛阶段仅需数万次标记操作,加上提前终止的逻辑,整体运行速度可以提升两个数量级以上。如果需要处理更大的x值,还可以进一步调整为线性筛生成素数表,或者直接遍历预先生成的素数列表,判断素数是否落在当前待验证的区间内,进一步减少无效扫描次数。

内容的提问来源于stack exchange,提问作者Raymond Dybala

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.09 13:06:04