204. 计数质数

题目

LeetCode-204

解析

初次拿到这道题时觉得非常简单，只要统计下从2到这个数字之间的数字是不是质数就可以了，按照这个想法就出现了这种算法，

    public int countPrimes(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isZhishu(i)) {
                count++;
            }
        }
        return count;
    }

    public boolean isZhishu(int n) {
        if (n == 1 || n == 2) {
            return true;
        } else {
            for (int i = 2; i < n; i++) {
                if (n % i == 0)
                    return false;
            }
        }
        return true;
    }

很显然，第一时间就想出来的算法肯定是有问题的，这个算法的时间复杂度是O(n^2)，很明显的只要数字稍微变大，时间就会变得非常长，这种算法肯定是要出事的，那么有没有什么好的算法呢？
答案当然是肯定的。

新的算法

将n以内大于2的数全部存入布尔数组，并将其布尔值值为true，然后进行遍历，在遍历过程中，如果遍历的数值为false，则continue；否则，则从当前下标开始，对当前下标的数的倍数（小于N）全部置为false，直到遍历结束，最后所得数值中值为true的个数即为素数的个数。

这么说可能有点难理解，简单的来说就是如果一个数i是质数，那么i(i+1)、i(i+2)往下都是合数，通通在布尔数组里面置为false即可。

下面上代码：

public int countPrimes(int n) {
        boolean[] a = new boolean[n];
        for (int i = 2; i * i < n; i++) {
            if (!a[i]) {
                for (int j = i; i * j < n; j++) {
                    a[i * j] = true;
                }
            }
        }
        int c = 0;

        for (int i = 2; i < n; i++) {
            if (a[i] == false) ++c;
        }
        return c;
    }