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.暴力解法: 挨個(gè)數(shù)字遍歷，計(jì)算是否為素?cái)?shù).
計(jì)算一個(gè)數(shù)字是否為素?cái)?shù)，time O(n)
全部算完: 時(shí)間 O (n*n) 空間 O(1)
2.使用一個(gè)長(zhǎng)度為n的boolean臨時(shí)數(shù)組舷暮，標(biāo)記是否為素?cái)?shù)效五。
遍歷元素i，從2開(kāi)始
如果flag為 非素?cái)?shù)囊颅，count++;
并且計(jì)算i乘以一個(gè)倍數(shù)j(j從2開(kāi)始当悔，依次++)，只要 i*j = m < n 則標(biāo)記 m 非素?cái)?shù)
等所有數(shù)字標(biāo)記完成迁酸，素?cái)?shù)個(gè)數(shù)count就統(tǒng)計(jì)完成了
time：O(nlogn)? space: O(n)
參考：https://zhengyang2015.gitbooks.io/lintcode/count-primes-leetcode-204.html 動(dòng)畫很清晰顯示了思路
下面的代碼跟參考文章思路類型先鱼，稍微優(yōu)化的版本。
public int countPrimes(int n){
boolean[] notPrimes = new boolean[n];//默認(rè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;
}
