1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int countPrimes(int n) {
        int[] numbers = new int[n];
        int upperBound = (int) Math.sqrt(n);
        for (int i = 2; i <= upperBound; i++) {
            if (numbers[i] == -1) {
                continue;
            }
            for (int j = i; i * j < n; j++) {
                numbers[i * j] = -1;
            }
        }
        int count = 0;
        for (int i = 2; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                count += 1;
            }
        }
        return count;
    }
}

这道题要需要知道一个结论, 就是除了0和1的任意一个自然数可以被拆成一个或若干个prime number的积. 比如20, 可以拆成2 * 2 * 5. 为什么是这样? 假设有个自然数只能拆成都是合数的积, 那么合数可以被继续拆分, 拆分出来的factor只会越来越小, 假设拆出来的数字还是合数, 我们可以重复这个过程. 由于最小的合数就是4, 那么最后被拆成了4, 但是4可以继续拆, 拆成2 * 2因此和我们的假设(该数字只能被拆成合数)相悖. 因此任意大于等于2的自然数都可以被拆成一个或若干个质数的积.

知道了上面的这个结论, 我们的方法就是先声明一个数组, 大小为n. 然后从2开始, 把小于n的2的倍数都标记为-1. 之后我们遍历数组, 找到下一个不是-1的位置, 该位置对应的index就是下一个质数. 为什么这个下一个不被标记为-1的数字就是质数? 我们知道现在数组中没被标记为-1的数字有除了2以外的质数, 当然也有不是2的倍数的合数比如15(假设n大于15).根据之前的结论, 我们往后遍历遇到一个数字没有被标记为-1, 那么这个数字如果是合数, 那么它可以被拆分成质数的积, 此时比该数字小的质数只有2, 但是我们知道之前2的倍数都被标记为了-1, 这与我们的假设相悖, 因此2之后遍历遇到的下一个不被标记为-1的数字一定是比2的质数中最小的那个, 也就是3.

到了3之后, 我们按照相同的逻辑, 把是3的倍数都标记为-1. 标记后继续往后遍历, 找到下一个非-1的质数. 那么什么时候停止这个遍历, 也就是在某个质数处, 我们把它的倍数都标记为-1后, 我们知道[0, n - 1]所有的合数都被标记为了-1. 我们如何知道这个质数是多少? 知道这个我们还需要知道一个结论. 刚才我们到了3, 需要把3的倍数都标记为-1. 我们正常就是从3的1倍, 2倍, 3倍…一直标记到小于n的最大3的倍数. 但是我们真的需要从1倍开始, 往后递增吗? 实际上我们只需要从3倍开始递增找即可. 更一般化就是到了某个质数i, 我们要把i的倍数都标记为-1, 我们只需要从i的i倍开始标记即可, 也就是i的i倍, i的i + 1倍, i + 2倍… 为什么? 为什么肯定i的1到i - 1倍都被标记好了? 假设有个数字j, 1<= j <= i - 1. 那么j如果是质数, j的i倍肯定之前被我们标记过了. 因为根据我们的逻辑遇到的质数的所有倍都会被我们标记为-1, 由于j在i前, 因此j的所有倍都被我们标记, 此时j * i被我们标记了. 如果j是合数, 那么j可以被拆分成多个质数的积. 这些质数都小于j. 假设p1 * p2 * p3 *… * pn == j. 其中p1 <= p2 <= p3…. <= pn < j < i. 我们可以这样看, p1是个质数且小于i, p1的所有倍都被标记为了-1, 因此j * i = p1 * p2 * … * pn * i也被标记为了-1.

综上, 当我们到达某个质数i并且要把它的所有倍数都标记为-1的时候, 我们从i的i倍开始标记即可. 因为i的i倍一定不会被之前的质数的倍数覆盖, 因此i的i倍只能是在i这里达到.

知道上面讨论的结论的时候, 我们就知道什么时候可以确定[0, n - 1]范围内的合数都被标记好了, 那就是取n的平方根假设是m(平方根带小数的话向下取整). 从2开始遇到质数就标记, 一直到m. 当完成m这个位置后, 我们就能确定所有的合数都被标记了. 因为m的平方是小于等于n的. m + 1的平方一定是大于n的, 因此到m这一步就可以把[0, n - 1]中的合数标记完, 这也就是我们外侧循环的终止条件. inner loop的终止条件就是i的某个倍数小于n即可, 因为我们要求的是小于n的质数的个数.

综上, 逻辑就出来了. 比较重要的两个结论就是任何大于等于2的自然数都可以被拆分为一个或若干个质数的积. 还有就是当遍历到某个质数i的时候, 我们标记i的倍数的合数时从i的i倍开始标记, 因为i的[1, i - 1]倍都被之前的质数标记好了.

时间复杂度: O(loglogn) 具体见题解.
空间复杂度: O(n) 因为我们分配了一个长度为n的数组.