Python质数检查代码优化咨询：问题排查与效率提升建议

首先修正原代码的语法错误并展示完整代码（含核心逻辑bug）：

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        # 核心bug：未检查i+2的整除性
        if n % i == 0:
            return False
        i += 6
    return True

# 输入存在语法错误（字符串未闭合）
number = int(input("Enter a number:\n"))
if is_prime(number):
    print(f"{number} is prime")
else:
    print(f"{number} is not prime")

一、代码存在的潜在问题 #

1. 核心逻辑错误：原函数仅检查n % i == 0，但根据6k±1的质数规律，所有大于3的质数都属于6k-1或6k+1形式，因此需同时检查i和i+2的整除性。例如数字49（7×7）会被原代码误判为质数——i从5开始，5×5≤49，检查49%5≠0后i增加到11，11×11>49，循环结束返回True，但49是合数。
2. 输入语法错误：input的字符串未正确闭合，换行符导致代码运行直接报错。
3. 缺乏输入健壮性：未处理非整数输入，当用户输入字母、符号时，int()会抛出ValueError导致程序崩溃。
4. 循环条件效率偏低：使用i * i <= n作为循环条件，对于极大数，乘法运算的开销略高于直接比较整数平方根。

二、具体改进建议 #

1. 修复核心逻辑错误 #

在循环中同时检查i和i+2的整除性：

i = 5
while i * i <= n:
    if n % i == 0 or n % (i + 2) == 0:
        return False
    i += 6

2. 完善输入处理 #

修正输入语法错误，添加异常捕获和负数提示：

try:
    number = int(input("Enter a number: "))
    if number < 0:
        print("Negative numbers cannot be prime.")
    else:
        result = is_prime(number)
        print(f"{number} is {'prime' if result else 'not prime'}")
except ValueError:
    print("Error: Please enter a valid integer.")

3. 优化循环条件 #

使用Python 3.8+的math.isqrt()获取整数平方根，避免重复乘法运算：

import math

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    max_divisor = math.isqrt(n)
    i = 5
    while i <= max_divisor:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

4. 提升代码可读性 #

添加注释说明6k±1的质数规律：

def is_prime(n):
    # 小于等于1的数不是质数
    if n <= 1:
        return False
    # 2、3是最小的质数
    if n <= 3:
        return True
    # 能被2或3整除的数直接排除
    if n % 2 == 0 or n % 3 == 0:
        return False
    # 所有大于3的质数都符合6k±1形式，从5开始按步长6遍历检查
    max_divisor = math.isqrt(n)
    i = 5
    while i <= max_divisor:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

三、大数的最优素性检查方案 #

当前方法属于确定性试除法，时间复杂度为O(√n)，仅适合较小的数（如n < 10^12）。对于100位以上的大数，试除法效率极低，因为√n的位数是n的一半，循环次数会爆炸式增长。

推荐方案：Miller-Rabin素性测试 #

这是一种高效的概率性素性测试，对于小于2^64的整数，可通过固定基集合实现确定性判断，无需担心误判。以下是针对64位以内整数的实现：

import math

def is_prime_miller_rabin(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
    # 64位以内数的确定性基集合
    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in bases:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

• 该实现对n < 2^64的数完全准确，处理100位大数也能快速得到结果。
• 若需处理更大的数，可增加更多测试基，或结合Lucas-Lehmer测试等方法。

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