204. 计数质数

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

这道题的关键点就在于如何更有效的判断一个数为质数
那么这里举几个例子
比如16，那么有1*16，2*8，4*4，8*2，16*1这几个整数相乘的结果等于16。
再来看一个，
25，1*25，5*5，25*1
20，1*20，2*10，4*5，5*4，10*2，20*1
那么这里可以发现有如下规律：
众多 i*j=n 中，总有一个小于并最接近sqrt(n)开根号的整数k，
使得以后的所有i*j开始变成j*i，也就是说，从k以后，
下一个i*j就会开始和前面的相同，所以这里可以将原本需要
从1开始循环判断到n的量缩减到
小于等于sqrt(n)

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

    private boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

埃氏筛法步骤
（1）先把1删除（现今数学界1既不是质数也不是合数）
（2）读取队列中当前最小的数2，然后把2的倍数删去
（3）读取队列中当前最小的数3，然后把3的倍数删去
（4）读取队列中当前最小的数5，然后把5的倍数删去
（5）读取队列中当前最小的数7，然后把7的倍数删去
（6）继续下一个质数，同上
（7）如上所述直到需求的范围内所有的数均删除或读取
注：此处的队列并非数据结构队列，如需保留运算结果，处于
存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。

public int countPrimes(int n) {
        if ((n ^ 0) == 0 || (n ^ 1) == 0) {
            return 0;
        }
        //对应的数0,1,2,..,(n-1)
        boolean[] prime = new boolean[n];
        Arrays.fill(prime, true);
        //0和1肯定不是质数
        prime[0] = false;
        prime[1] = false;
        //从2开始
        for (int i = 2; i < n; i++) {
            if (prime[i]) {
                // 将i的2倍、3倍、4倍...都标记为非素数
                for (int j = i * 2; j < n; j = j + i) {
                    prime[j] = false;
                }
            }
        }
        //统计
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (prime[i]) {
                count++;
            }
        }
        return count;
    }