判断一个数是否为质数——优化常见O(sqrt(n)/2)复杂度算法存在的问题

$O(\dfrac{\sqrt n}{2})$ 复杂度算法作为常见 $O(\sqrt n)$ 复杂度算法的优化版本，能够减少后者的一半复杂度，但常见优化算法或多或少存在一些问题：有的无法对个位数正确判断、有的无法对负数正确判断……

这篇博客将给出一种优化版本解决提到的问题。

定义

因数只有 $1$ 和本身的自然数称为质数，或称素数。

算法

分析

根据定义，若一个数 $n$ 为合数，则可以进行因数分解，且所得两个因数 $n_1 > n_2$ 必有

$$n_1 \ge \sqrt n, n_2 \le \sqrt n$$

若在 $\sqrt{n}$ 左侧找不到因数，右侧也一定找不到，因此只需判断从 $2$ 到 $\sqrt n$ 是否存在 $n$ 的约数。

此外，任何大于 $2$ 的偶数均为合数 ，故只需遍历奇数即可。

实现

bool isPrime(int n) {
    // 判断是否为负数、0、1或大于2的偶数
    if (n < 2 || n % 2 == 0 && n > 2) {
        return false; 
    }
    // 遍历大于2的奇数
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}