Description
Description:
Count the number of prime numbers less than a non-negative number, n.
Solution
Basic
注意不能用n / 2来减小遍历范围，比如n = 4的话，如果用n / 2来缩小范围，3就没有被处理。
神奇的地方是，用HashSet会超时，改成array就好了。看来如果array范围可控还是用array比较快。
还要注意题目求的是小于n的个数！
class Solution {
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n];
int count = 0;
for (int i = 2; i < n; ++i) {
if (notPrime[i]) {
continue;
}
++count;
for (int j = 2; i * j < n; ++j) {
notPrime[i * j] = true;
}
}
return count;
}
}
Optimized
偶数可以skip
TODO
