Python素数判断两种实现对比、最优选择及存在问题咨询

代码选择建议 #

首先纠正你的认知错误：第二种代码效率更优的判断完全错误。第一种代码循环上限是num//2 + 1，第二种是num，数值越大第二种的无效循环次数越多，性能远差于第一种，更推荐优先选择第一种的实现思路。

两段代码共同存在的严重逻辑漏洞 #

• 核心判断逻辑写反：如果num能被i整除，说明num存在除了1和自身之外的因子，应该判定为非素数，但两段代码都在num % i == 0的分支打印Prime!，反而在循环正常结束（无整除匹配）的else分支打印Not Prime!，完全颠倒了判断结果。
• 边界值处理完全缺失：
  1. 没有拦截小于2的输入（包括1、0、负数），这类数值全部会被误判为素数
  2. 输入值为2时，range(2, lim)/range(2, num)都是空序列，直接进入else分支，会被误判为非素数，但2是唯一的偶素数

可优化方向 #

修复上述逻辑漏洞后，还可以做以下性能优化：

1. 循环上限不需要到num//2，只需要到int(num**0.5) + 1即可：如果num有大于平方根的因子，必然对应存在一个小于平方根的因子，仅检查到平方根就足够完成判断，循环次数会大幅减少
2. 可以先单独判断num是否为偶数，后续循环只遍历奇数，能直接减少一半的循环次数

修复后的参考实现 #

num = int(input("Enter the number: "))
# 先处理边界情况
if num <= 1:
    print("Not Prime!")
elif num == 2:
    print("Prime!")
# 偶数直接排除
elif num % 2 == 0:
    print("Not Prime!")
else:
    # 只遍历奇数到平方根
    lim = int(num**0.5) + 1
    for i in range(3, lim, 2):
        if num % i == 0:
            print("Not Prime!")
            break
    else:
        print("Prime!")

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