当给定一个数字 $n$ 时，我们如何能够快速判断这个数字是否是一个素数呢？

最朴素的方式当然是将小于 $n$ 且大于等于 $2$ 的所有数字除 $n$，若余数全部为 $0$，则说明是素数。但这样的方法时间复杂度在 $O(n)$，以下对算法进行改进。

改进一：修改除数范围

这里的一个关键观察在于：如果一个数字可以进行因数分解，那么一定有一个数字小于等于 $\sqrt{n}$，而另一个数大于等于 $\sqrt{n}$，带着这个观察，我们可以把遍历的范围改为 $[2, \sqrt{n}]$，得到一个时间复杂度为 $O(\sqrt{n})$ 的算法。

boolean prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

改进二：缩小检查范围

证明如下：
令 $x \geq 1$； 则大于等于5的自然数表示如下：

可以看到，不在6的倍数两侧的数：$6x,2(3x+1),3(2x+1),2(3x+2)$ 都不是素数。
可能为素数的就只有：$6x−1$ 和 $6x+1$。

因此，得到一个数字 $n$ 后，我门首先判断他是否和 $6$ 的倍数相邻，如果是，继续检查，否则直接判定为非素数。

boolean prime(int n) {
    if (n == 2 || n == 3) {
        return true;
    }
    if (n % 6 != 1 && n % 6 != 5) {
        return false;
    }
    for (int i = 5; i <= Math.floor(Math.sqrt(n)); i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}