质数判断函数异常：误将9识别为质数的问题排查求助

我编写了一个基于模运算判断质数的函数，整体框架逻辑可行，但运行时错误地将9归类为质数。函数代码如下：

def is_prime(x):
  if x <= 1: return False
  elif x == 2 or x == 3: return True
  else:
    for n in range(2, x - 1):
      if x % n == 0:
        return False
      else:
        return True

调用is_prime(9)时函数返回True，但在解释器中执行9 % 3结果为0，显然9不是质数。以下是解释器运行过程：

Python 3.11.2 (tags/v3.11.2:878ead1, Feb  7 2023, 16:38:35) [MSC v.1934 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> def is_prime(x):
...     for n in range(2, x-1):
...             if x % n == 0: return False
...             else: return True
... 
>>> is_prime(9)
True

按道理当n=3、x=9时，x%n应该为0，为什么函数没检测到？

错误原因分析 #

问题出在循环内的return逻辑：当循环第一次执行n=2时，9%2=1，触发else分支直接返回True，循环根本没机会执行到n=3的情况。函数在第一次判断不整除时就直接返回了结果，跳过了后续所有可能的因数检查。

正确的逻辑应该是：

• 遍历过程中只要找到一个能整除x的数，立即返回False
• 只有当遍历完所有可能的因数都没找到整除项时，才返回True

修正后的代码 #

基础修正版本

先修复核心逻辑问题，保留原循环范围：

def is_prime(x):
    if x <= 1:
        return False
    elif x == 2 or x == 3:
        return True
    else:
        for n in range(2, x - 1):
            if x % n == 0:
                return False
        # 循环结束后没找到因数，才返回True
        return True

优化效率版本

实际上判断质数不需要遍历到x-1，只需要遍历到x的平方根即可（因为如果x有大于平方根的因数，必然对应一个小于平方根的因数），可以大幅提升大数字的判断效率：

import math

def is_prime(x):
    if x <= 1:
        return False
    elif x == 2 or x == 3:
        return True
    else:
        # 遍历到平方根即可，+1确保覆盖整数平方根的情况
        for n in range(2, int(math.sqrt(x)) + 1):
            if x % n == 0:
                return False
        return True

测试is_prime(9)会返回False，符合预期。

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