如何优化验证勒让德猜想的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
相关产品推荐
相关产品推荐

