试除法判定素数与优化

从一张奖券说起

想象一下，你参加了一个数学游戏：老师拿出一个数字，比如23，问大家：“谁能最快告诉我，23是不是一个‘孤独的数字’？”这里的“孤独的数字”其实指的就是素数（也叫质数）。素数就像那些不愿意和别人交朋友、只愿意和1以及自己两个朋友相处的数字。比如2、3、5、7，它们只能被1和自己整除，没有其他朋友（因子）。相反，合数像12，它可以有很多朋友：1、2、3、4、6、12。

现在，要判断一个数是不是素数，最直接的办法就是试除——也就是拿着这个数，挨个儿去问比它小的数：“你能整除我吗？”如果有一个数除了1和它自己之外能整除它，那它就不是素数。这个办法就好比在一个班级里，你要确认一个同学是不是“孤独”——你让他去问班里的每一个其他同学：“我们俩是不是好朋友？”如果除了他自己之外，没有任何同学愿意和他组成“整除对”，他就是孤独的（素数）。这就是试除法的基本思想。

不过，如果这个数很大，比如999999937，你真的要从2一直试到它本身吗？那得试到猴年马月！别担心，数学上有很多聪明的办法可以大大加快速度。今天我们就来学习试除法以及它的优化，让你在几秒钟内就能判断一个超大数是不是素数。

数学原理与公式推导

什么是素数？

一个大于1的自然数，如果除了1和它自身以外，不再有其他正因数，那么这个数就叫素数（质数）。比如2、3、5、7、11……注意：1既不是素数也不是合数。

朴素试除法的原理

要判断一个数 n 是否为素数，最朴素的想法是：检查从2到 n-1 中的每一个整数 i，看 n 除以 i 的余数是否为0。如果存在某个 i 使得 n % i == 0，则 n 是合数；如果全部都不整除，则 n 是素数。

这个办法很直观，但缺点也明显：当 n 很大时，需要做 n-2 次除法运算，时间非常长。比如 n = 1000000，就要做近100万次除法，计算机虽然快，但也不能这样浪费。

第一个优化：只检查到平方根

数学上有一个重要结论：如果 n 是合数，那么它一定有一个不大于 sqrt(n) 的因子。

为什么呢？假设 n 是合数，那么它可以写成 n = a * b，其中 a 和 b 都是大于1的正整数。如果我们假设 a <= b，那么 a * a <= a * b = n，所以 a <= sqrt(n)。反过来，如果 a > sqrt(n)，那么 b = n / a < n / sqrt(n) = sqrt(n)，所以 b 就会小于 sqrt(n)。这意味着，合数 n 的因子对中，较小的那个因子一定小于或等于 sqrt(n)。

因此，我们只需要检查从2到 sqrt(n) 的整数就可以了。如果在这个范围内都找不到因子，那么 n 就是素数。

这个优化让试除的次数从 n-2 降到了 sqrt(n)-1。对于 n = 1000000，sqrt(n) = 1000，只需要约1000次除法，速度提升了1000倍！

我们可以用生活中的例子来理解这个优化：假设你有一堆乐高积木，想拼成一个长方形。如果长方形的面积是 n，那么它的长和宽就是一对因子。你想知道是否存在长和宽都大于 sqrt(n) 的长方形？不可能，因为如果两个数都大于 sqrt(n)，它们的乘积就会大于 n。所以，只要检查边长不超过 sqrt(n) 的那些可能，就能找到所有可能的拼法。

第二个优化：跳过偶数

除了2以外，所有的偶数都不可能是素数（因为都能被2整除）。所以我们可以在开始判断时先单独处理 n == 2 的情况，然后对于其他所有数，先判断是否为偶数（n % 2 == 0），如果是偶数且大于2，直接返回 false。然后再从3开始，每次步长取2（即只检查奇数），一直检查到 sqrt(n)。这样需要检查的次数大约再减半。

更进一步的优化

还可以考虑跳过3的倍数、5的倍数等，比如使用“6k ± 1”规律（即所有大于3的素数都可以写成 6k ± 1 的形式），但代码会变得更复杂。对于初学者来说，掌握“平方根 + 跳过偶数”已经足够应对常见题目了。

算法步骤（优化版）

如果 n <= 1，不是素数。
如果 n == 2，是素数。
如果 n % 2 == 0，不是素数。
设 limit = sqrt(n)，i 从3开始，每次 i += 2，直到 i <= limit：
- 如果 n % i == 0，返回不是素数。
如果循环结束都没有找到因子，返回是素数。

新手容易犯的错误

初学者写判断素数的代码时，常常会掉进下面这些坑里。看看你有没有中招？

错误1：忘记处理特殊情况 n <= 1
1 不是素数也不是合数，0 和负数更不是。如果直接拿 1 去试除，循环根本不会执行（因为从2开始），结果会错误地返回“是素数”。所以一定要先判断 n <= 1。

错误2：忘记处理 n == 2
2 是唯一的偶数素数。如果你没有单独处理它，而是直接进入 n % 2 == 0 的判断，2 会被当成偶数直接返回“不是素数”，这就错了。

错误3：循环边界写成 i < sqrt(n) 而不是 i <= sqrt(n)
比如判断 49，sqrt(49)=7，如果循环只检查到 i < 7，就漏掉了 i=7，而 49%7==0 应该被识别为合数。所以一定要用 <=。

错误4：每次循环都重新计算 sqrt(n)
有些人会在循环条件里写 for(int i=2; i<=sqrt(n); i++)，这样每循环一次就调用一次 sqrt 函数，浪费计算时间。应该先把它存到一个变量里（如 limit = sqrt(n)）。

错误5：不注意浮点数精度
sqrt 返回浮点数，直接赋值给整型变量会自动向下取整。对于完全平方数，比如 49，sqrt(49)=7.0，取整后是 7，没问题。但对于像 50，sqrt(50)≈7.07，取整后是 7，这其实已经足够，因为如果存在因子大于7，必然有对应的小于7的因子。但有些语言（比如C++）中 sqrt 可能因为浮点误差返回 6.999999，取整后变成 6，导致漏掉边界。安全做法是用 int limit = static_cast<int>(sqrt(n)) + 1 或者改用 while(i*i <= n) 的方式。

错误6：忘记循环步长
优化后应该只检查奇数，步长为2。有些新手从3开始，但步长写成1，结果还是检查了所有整数，这样虽然不报错，但效率没提高。

C++ 完整代码实现

#include <iostream>
#include <cmath>   // 用于 sqrt 函数
using namespace std;

// 函数：判断 n 是否为素数
bool isPrime(int n) {
    // 1 和 0 不是素数，负数也不是（我们通常只考虑正整数）
    if (n <= 1) return false;

    // 2 是唯一的偶数素数
    if (n == 2) return true;

    // 大于 2 的偶数都不是素数
    if (n % 2 == 0) return false;

    // 只需要检查到平方根，并且只检查奇数（从3开始，步长2）
    int limit = sqrt(n);   // 计算平方根，只需检查到此数
    for (int i = 3; i <= limit; i += 2) {  // i 从 3 开始，每次加 2，只检查奇数
        if (n % i == 0) {
            return false;  // 发现一个因子，不是素数
        }
    }

    // 没有找到任何因子，是素数
    return true;
}

int main() {
    int number;  // 用于存储用户输入的正整数
    cout << "请输入一个正整数: ";
    cin >> number;

    if (isPrime(number)) {
        cout << number << " 是素数。" << endl;
    } else {
        cout << number << " 不是素数。" << endl;
    }

    // 测试几个特殊值，看看函数是否正确
    cout << "\n测试一些数值:" << endl;
    int testNums[] = {1, 2, 3, 4, 17, 25, 97, 100, 101, 199, 9999991};
    for (int n : testNums) {
        cout << n << (isPrime(n) ? " 是素数" : " 不是素数") << endl;
    }

    return 0;
}

代码说明：

sqrt(n) 来自 <cmath> 头文件，返回 double，赋值给 int 时自动取整（向下取整），这足够了，因为如果 limit 略小于真正的平方根，循环条件 i <= limit 可能会漏掉一个边界情况。实际上，如果 n 是完全平方数，比如 49，sqrt(49)=7.0，limit 得到 7，循环会检查到 i=7，如果 49 % 7 == 0 会返回 false，正确。如果 n=97，sqrt(97)≈9.84，limit=9，循环检查到 i=9，没问题。所以用 int 截断是安全的（因为如果 n 是平方数，正好等于 sqrt(n)；如果不是，limit 小于真平方根，但循环停止时可能漏掉恰好在 limit+1 到 sqrt(n) 之间的因子？实际上，如果存在因子 >sqrt(n)，必然存在对应的因子 <sqrt(n)，所以只要检查到 floor(sqrt(n)) 就够了。不用担心。）
循环从 3 开始，步长 2，只检查奇数。
isPrime 函数返回 bool 类型，简洁清晰。

Python 完整代码实现

import math   # 用于 sqrt 函数

def is_prime(n):
    # 1 和 0 不是素数
    if n <= 1:
        return False

    # 2 是唯一的偶数素数
    if n == 2:
        return True

    # 大于2的偶数都不是素数
    if n % 2 == 0:
        return False

    # 只需要检查到平方根，步长为2（只检查奇数）
    limit = int(math.sqrt(n))   # 计算平方根并取整，作为循环上界
    for i in range(3, limit + 1, 2):  # 从3开始，到limit（包含），每次加2
        if n % i == 0:
            return False   # 发现因子，不是素数

    # 没有因子，是素数
    return True

# 主程序
if __name__ == "__main__":
    number = int(input("请输入一个正整数: "))  # 输入要判断的数
    if is_prime(number):
        print(f"{number} 是素数。")
    else:
        print(f"{number} 不是素数。")

    # 测试一些数值，看看函数是否正确
    print("\n测试一些数值:")
    test_nums = [1, 2, 3, 4, 17, 25, 97, 100, 101, 199, 9999991]
    for n in test_nums:
        print(f"{n} {'是素数' if is_prime(n) else '不是素数'}")