大整数素数检测仅校验2、3、5、7整除性是否存在遗漏边界？

核心结论 #

该方案完全不可行，存在大量误判场景，同时现有代码本身也存在逻辑漏洞。

具体问题说明 #

1. 方案本身的逻辑缺陷 #

素数的定义是大于1的自然数，除了1和自身之外没有其他正因数。素数校验的基础规则是：若整数n存在任意一个小于等于√n的质因数，则n为合数。
你仅检测了2、3、5、7四个小素数，这意味着只要数大于77=49，且最小质因数大于7时，你的代码就会把合数误判为素数，最小的反例是121（1111），它无法被2、3、5、7整除，但属于明确的合数。
你提到的大整数157632829的平方根约为12555，仅检测到7完全无法覆盖所有可能的质因数范围，误判概率极高。

2. 常见的误判反例 #

以下都是不被2、3、5、7整除的合数，都会被你的代码误判为素数：

• 121 = 11 * 11
• 143 = 11 * 13
• 169 = 13 * 13
• 187 = 11 * 17
• 209 = 11 * 19

3. 现有代码的额外逻辑错误 #

你的边界判断逻辑本身也不符合素数定义：

• 素数只存在于大于1的自然数中，n=0、n=1、所有负数都不是素数，你当前n<4返回True的逻辑会把n=0、1、负数都误判为素数。

基础素数校验优化建议 #

如果是处理量级不大的整数校验，可以按如下逻辑优化：

def is_prime(n):
    # 处理边界情况
    if n <= 1:
        return False
    if n <= 3:
        return True
    # 先排除偶数、3/5/7的倍数
    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0:
        return False
    # 从11开始遍历到√n，步长为2跳过偶数
    i = 11
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

如果需要处理超大整数（比如10^12以上），可以使用米勒-拉宾素性测试进一步提升效率。

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