204. Count Primes

原题链接：https://leetcode.com/problems/count-primes/description/
这道题目数学相关性比较强，忘记什么是质数的同学估计就得先学习下质数了，然后就是思考思路了，我思考了两种方法，就是提示里面的前两种提示啦，不过效率上都不过关，然后一路跟着提示走，最后扯到了牛逼哄哄的埃拉托色尼筛选法。。。。好吧，下面是实现：

/**
 * Created by clearbug on 2018/2/26.
 */
public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        long startTime = System.currentTimeMillis();
        System.out.println(s.countPrimes(1500000));
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }

    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }
        // Loop's ending condition is i * i < n instead of i < sqrt(n) to avoid repeatedly calling an expensive function sqrt().
        for (int i = 2; i * i < n; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }

    private boolean isPrime(int n) {
        int root = (int) Math.sqrt(n);
        for (int i = 2; i <= root; i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }
}