204. Count Primes
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.
思路
1.暴力解法: 挨个数字遍历，计算是否为素数.
计算一个数字是否为素数，time O(n)
全部算完: 时间 O (n*n) 空间 O(1)
2.使用一个长度为n的boolean临时数组，标记是否为素数。
遍历元素i，从2开始
如果flag为 非素数，count++;
并且计算i乘以一个倍数j(j从2开始，依次++)，只要 i*j = m < n 则标记 m 非素数
等所有数字标记完成，素数个数count就统计完成了
time：O(nlogn)? space: O(n)
参考：https://zhengyang2015.gitbooks.io/lintcode/count-primes-leetcode-204.html 动画很清晰显示了思路
下面的代码跟参考文章思路类型，稍微优化的版本。
public int countPrimes(int n){
boolean[] notPrimes = new boolean[n];//默认全部为false
int count = 0;
for(int i = 2; i < n;i++){
if(notPrimes[i] == false){
count++;
}
for(int j = 2;j < n;j++){
if(i * j < n){
notPrimes[i*j] = true;
}
}
}
return count;
}
