Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
找素数，每次找到素数的时候，可以把素数的倍数都标记为非素数。这样可以节省轮询的时间。
class Solution { public int countPrimes(int n) { if (n <= 1) { return 0; } boolean[] notPrime = new boolean[n]; notPrime[0] = true; notPrime[1] = true; // 可以优化为 i * i < n for (int i = 2; i < n; i++) { if (!notPrime[i]) { for (int j = 2 * i; j < n; j += i) { notPrime[j] = true; } } } int result = 0; for (int i = 0; i < n; i++) { if (!notPrime[i]) { result++; } } return result; } }