Python素数判断函数isPrime触发Time Limit Exceeded超时错误求解决方案

报错描述：运行代码时触发Time Limit Exceeded错误，程序运行耗时超出1.02秒的预期限制，触发原因为素数判断函数效率过低。

原有代码缺陷 #

现有isPrime函数存在以下性能问题：

• 循环范围设置为range(2, number)，当输入数值较大时，循环次数达到O(n)级别，时间复杂度过高
• 存在无效代码：return False后的break语句永远不会执行
• 未处理边界情况和偶数快速判断逻辑，无意义循环量过大

优化思路 #

素数判断的核心优化规则：

1. 小于2的数不是素数，直接返回False
2. 2是唯一的偶素数，直接返回True
3. 所有大于2的偶数都不是素数，直接返回False
4. 因数是成对出现的，只需循环遍历到数值的平方根即可，若到平方根都没有找到因数，则该数为素数
5. 排除偶数后，循环只需遍历奇数，进一步减少一半循环量

优化后完整代码 #

import math

def isPrime(number):
    # 边界情况判断
    if number < 2:
        return False
    if number == 2:
        return True
    # 偶数快速排除
    if number % 2 == 0:
        return False
    # 仅遍历到平方根，且只校验奇数
    for i in range(3, int(math.sqrt(number)) + 1, 2):
        if number % i == 0:
            return False
    return True

def main():
    testcases = int(input())
    while testcases > 0:
        number = int(input())
        print(isPrime(number)) 
        testcases -= 1

if __name__=='__main__':
    main()

优化效果 #

优化后素数判断的时间复杂度从O(n)降至O(√n)，针对大数值的判断效率可提升数百倍，完全满足1.02秒的运行时间限制。

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