Python高效质数判定代码编写求助：需优化现有基础实现

你的基础实现虽然能正确判断质数，但效率太低——遍历到num-1完全没必要，针对不同场景，下面给你几种逐步优化的方案：

优化1：缩小遍历范围+奇偶过滤 #

核心思路 #

如果一个数num是合数，那它必然有一个不大于√num的因数，所以只需要遍历到√num就行；另外除了2以外，所有偶数都不是质数，可以直接跳过偶数遍历，减少一半循环次数。

实现代码 #

import math

num = int(input('Enter the number to check whether it is prime or not: '))

if num <= 1:
    print("Not Prime")
elif num == 2:
    print("Prime number")
elif num % 2 == 0:
    print("Not Prime")
else:
    is_prime = True
    # 用math.isqrt避免浮点精度问题，返回整数平方根
    sqrt_num = math.isqrt(num)
    # 从3开始，只遍历奇数，步长设为2
    for i in range(3, sqrt_num + 1, 2):
        if num % i == 0:
            is_prime = False
            break
    print("Prime number" if is_prime else "Not Prime")

优化2：米勒-拉宾素性检验（超大数专用） #

如果需要判断几百位的超大质数，上面的方法还是不够快，这时候可以用米勒-拉宾素性检验——这是一种概率性算法，但对于小于2^64的数，用固定的几个测试底数就能得到100%准确的结果，性能碾压前两种方案。

实现代码 #

def is_prime(n):
    # 处理小数字的边界情况
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0:
        return False
    
    # 将n-1分解为d*2^s的形式
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    # 对于n < 2^64，这些底数可以保证判定准确
    test_bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in test_bases:
        if a >= n:
            continue
        # 快速幂取余，避免计算溢出
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        # 进行s-1次平方取余
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            # 所有循环都没触发break，说明是合数
            return False
    return True

num = int(input('Enter the number to check whether it is prime or not: '))
print("Prime number" if is_prime(num) else "Not Prime")

适用场景总结 #

• 基础实现：仅适合教学演示，小数字（比如小于1000）用用还行
• 平方根优化方案：日常开发中判断中小数字质数，足够高效
• 米勒-拉宾：需要处理超大质数（比如密码学场景）时的首选

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