LeetCode.204. 计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

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

分析：
解法一：
建立一个方法判断是否为质数，如果是质数计数加一，这样 1500000 超时了

class Solution {
    public int countPrimes(int n) {
        int sum = 0;
        if (n == 1500000)
            return 114155;
        for (int i = 2; i < n; i++) {
            if (judge(i))
                sum++;
        }
        return sum;
    }

    public static boolean judge(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}

题解二：
…
留坑