数论算法思维

问题：给定一个正整数 n，判断它是否为素数。

解法一：最朴素的暴力尝试

素数的定义是什么？一个大于1的自然数，除了1和它自身外，不能被其他自然数整除。

行，定义就是解法。

我脑子里第一个蹦出来的想法，就是直接按定义来。我要判断 n 是不是素数，我就去试呗。从 2 开始，一直到 n-1，看看这里面有没有哪个数能把 n 整除。如果一路下来都没有，那 n 就是素数。如果中途随便找到一个，那 n 就不是素数，直接可以收工了。

比如判断 7 是不是素数：

用 2 除 7，余 1。
用 3 除 7，余 1。
用 4 除 7，余 3。
用 5 除 7，余 2。
用 6 除 7，余 1。全部试完了，都不能整除。所以 7 是素数。

再比如判断 6 是不是素数：

用 2 除 6，余 0。好了，找到了一个因子，直接可以确定 6 不是素数。后面的 3, 4, 5 都不用再试了。

思路清晰，代码也简单：

// 解法一：暴力法
public boolean isPrime1(int n) {
    // 小于等于1的数都不是素数
    if (n <= 1) {
        return false;
    }
    // 从2开始，一直到n-1
    for (int i = 2; i < n; i++) {
        // 如果能被整除，说明n有除了1和自身以外的因子，不是素数
        if (n % i == 0) {
            return false;
        }
    }
    // 循环走完都没找到因子，是素数
    return true;
}

这个解法，逻辑上完美。但性能呢？时间复杂度是 O(N)。如果 n 是个比较大的数，比如 10^9，那你这个循环得跑10亿次，面试官咖啡都喝完三杯了，你的程序还在那傻跑呢。

不行，必须优化。

解法二：一个显而易见的优化

我们再仔细想想，判断n是不是素数，真的需要从2一直检查到n-1吗？

举个例子，n = 100。它的因子有哪些？(2, 50), (4, 25), (5, 20), (10, 10)。你发现了没？因子都是成对出现的。比如你找到了 2 是 100 的因子，那你必然也知道 50 也是。你找到了 4，就等于找到了 25。

这个“对”的分界点在哪？就在 sqrt(n)。如果 d 是 n 的一个因子，那么 n/d 必然也是。这一对因子中，必然有一个是小于或等于 sqrt(n) 的，另一个是大于或等于 sqrt(n) 的。

所以，我们根本不需要检查到 n-1。我们只需要检查到 sqrt(n) 就足够了。如果在 [2, sqrt(n)] 这个区间里都找不到 n 的因子，那在 (sqrt(n), n-1) 这个区间里也绝对不可能有。因为如果后面有，前面必然有一个与之配对的。

是不是感觉豁然开朗？

比如判断 101 是不是素数（sqrt(101) 约等于 10.05）：我们只需要检查 2, 3, 4, 5, 6, 7, 8, 9, 10。 101 都不能被它们整除，所以 101 就是素数。检查的范围从 100 次直接降到了 9 次。

代码改造一下：

// 解法二：优化到 O(sqrt(N))
public boolean isPrime2(int n) {
    if (n <= 1) {
        return false;
    }
    // 注意，这里的循环条件是 i*i <= n，而不是 i <= Math.sqrt(n)
    // 因为 Math.sqrt() 操作是浮点数计算，比较慢，而且可能存在精度问题
    // i*i <= n 是纯整数运算，更快、更精确。
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

现在的时间复杂度是 O(sqrt(N))。对于 10^9 这种级别的数，sqrt(10^9) 大概是 3万多，这个计算量计算机处理起来就是一瞬间的事。

这个解法已经能应付绝大多数场景了。但是，还能不能再快一点？

解法三：结合数学性质的再次优化

我们再审视一下需要检查的数。除了 2 以外，所有的偶数都不可能是素数。这是一个常识。那一个数 n（假设它不是2），如果它是素数，它必然是个奇数。一个奇数可能被偶数整除吗？不可能。

所以，如果 n 是一个奇数，我们去检查它有没有因子的时候，根本不需要拿偶数去试。比如判断 101，我们试了 2, 3, 4, 5, 6, 7, 8, 9, 10。其实像 4, 6, 8, 10 这些偶数，完全是白费力气。

基于这个思路，我们可以进一步优化：

先把所有偶数（除了2）直接排除掉。
对于一个奇数 n，我们只需要用从 3 开始的所有奇数去试除就可以了。

具体步骤：

特判：小于等于1的不是素数。2是素数。
大于2的偶数，直接返回 false。
如果n是一个奇数，我们从 3 开始循环，每次步长为 2（只检查 3, 5, 7, 9...），直到 sqrt(n)。

看代码：

// 解法三：利用奇偶性再次提速
public boolean isPrime3(int n) {
    // 提前处理掉特殊情况
    if (n <= 1) return false;
    if (n == 2) return true;
    // 所有大于2的偶数都不是素数
    if (n % 2 == 0) return false;

    // 如果n是奇数，我们只需要检查奇数因子
    // 从3开始，步长为2
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

跟解法二比，这个解法的时间复杂度量级还是 O(sqrt(N))，但是循环的次数几乎又减少了一半。常数项优化也是优化，在工程上是非常有意义的。

至此，对于“判断单个数是否为素数”这个问题，解法三已经是非常高效和优雅的方案了。

拓展：批量判断素数 - 埃氏筛法

如果问题升级了呢？给你一个数 N，让你找出从 1 到 N 之间所有的素数。

你当然可以写个循环，从 1 到 N，对每个数都调用一次 isPrime3(i)。这个方法的时间复杂度是 O(N * sqrt(N))。当 N 很大时，比如 10^6，这个复杂度就有点高了。

这时候就需要换个思路了，从“判断一个数是不是素数”变成“筛掉所有不是素数的数”。这就是大名鼎鼎的埃拉托斯特尼筛法（Sieve of Eratosthenes），简称埃氏筛。

思路非常巧妙：

创建一个布尔数组 isPrime[]，长度为 N+1，初始化所有值为 true，表示我们暂时认为所有数都是素数。
把 isPrime[0] 和 isPrime[1] 标记为 false。
从 i = 2 开始遍历。如果 isPrime[i] 是 true，说明 i 是一个素数。
然后，把所有 i 的倍数（2*i, 3*i, 4*i, ...）都标记为 false，因为它们肯定不是素数。
继续遍历下一个 i，重复这个过程，直到 i*i > N。

举例，N = 20：

[true, true, ..., true]
i = 2，是素数。把 4, 6, 8, 10, 12, 14, 16, 18, 20 全标为 false。
i = 3，是素数。把 6, 9, 12, 15, 18 全标为 false。（有些是重复标记，没关系）
i = 4，isPrime[4] 已经是 false，跳过。
i = 5，是素数。把 10, 15, 20 全标为 false。 ... 最后数组里还剩下 true 的下标，就是所有的素数。

代码实现：

// 埃氏筛法: 找出 1~N 之间所有的素数
public int countPrimes(int n) {
    if (n <= 2) {
        return 0;
    }
    boolean[] isPrime = new boolean[n];
    // 初始化，假设所有数都是素数
    for (int i = 2; i < n; i++) {
        isPrime[i] = true;
    }

    // 从 2 开始，筛掉合数
    // 外层循环的终止条件也可以优化到 i * i < n
    for (int i = 2; i * i < n; i++) {
        // 如果 i 是素数
        if (isPrime[i]) {
            // 就把 i 的所有倍数都标记为合数
            // j 可以从 i*i 开始，因为小于 i*i 的倍数（比如 2*i, 3*i）
            // 肯定在之前处理更小的素数（比如 2, 3）时已经被筛掉了
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 统计素数个数
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
            count++;
        }
    }
    return count;
}

埃氏筛法的时间复杂度是 O(N log log N)，非常接近线性，效率极高。它用空间换时间，是解决批量素数问题的终极杀招。

总结

回顾一下我们的思维历程：

暴力解 O(N)：最直观，但效率最低。
开方优化 O(sqrt(N))：利用因子成对出现的性质，是思维上的一个巨大飞跃。
奇偶性优化 O(sqrt(N))：在开方优化的基础上，进一步利用数学性质削减了常数时间，是工程实践中的好习惯。
埃氏筛 O(N log log N)：当问题从“单点判断”变为“批量查询”时，需要根本上转变思路，从“判断”变为“筛选”。

这个思维的进阶过程，从暴力到利用数学性质优化，再到针对不同问题场景切换算法模型，才是最有价值的东西。