問題：
Count the number of prime numbers less than a non-negative number, n.
大意：
計(jì)算小于非負(fù)數(shù)n的質(zhì)數(shù)個(gè)數(shù)。
思路：
題目很簡(jiǎn)短，就是個(gè)找質(zhì)數(shù)的問題杖虾。
我們知道最簡(jiǎn)單的質(zhì)數(shù)就是2蕊程，3，5殃饿。茄唐。。那怎么計(jì)算往后的質(zhì)數(shù)呢舀锨？質(zhì)數(shù)的定義是除了自己以外沒有任何因子岭洲，也就是不被任何數(shù)整除，也就是說(shuō)坎匿，不會(huì)被這個(gè)數(shù)前面的任何質(zhì)數(shù)和非質(zhì)數(shù)整除盾剩，其實(shí)非質(zhì)數(shù)也可以被質(zhì)數(shù)整除，比如4被2整除替蔬，所以問題可以歸結(jié)為：沒遇到一個(gè)數(shù)告私，判斷它是否能被前面的某一個(gè)質(zhì)數(shù)整除。
要達(dá)到這個(gè)條件进栽，我們需要記錄在遍歷過程中遇到的質(zhì)數(shù)德挣，所以弄了一個(gè)數(shù)組來(lái)記錄遇到過的質(zhì)數(shù)，當(dāng)然2快毛、3格嗅、5是一開始就要放進(jìn)來(lái)的，我們遍歷時(shí)也應(yīng)該從2開始唠帝，因?yàn)?和1不是質(zhì)數(shù)屯掖。然后沒遇到質(zhì)數(shù)都記錄下來(lái)，同時(shí)遇到的每個(gè)數(shù)都去試一試能不能被前面的質(zhì)數(shù)整除襟衰。
這種做法在數(shù)字不大的情況下是奏效的贴铜，但是當(dāng)數(shù)字大了以后，就會(huì)超時(shí)了瀑晒。還是先看代碼吧绍坝。
代碼（Java）：
public class Solution {
public int countPrimes(int n) {
int result = 0;
int num = 3;
int[] prime = new int[n+3];
prime[0] = 2;
prime[1] = 3;
prime[2] = 5;
for (int i = 2; i < n; i++) {
if (i < 6 && i != 4) result ++;
boolean isPrime = true;
for (int j = 0; j < num; j++) {
if (i % prime[j] == 0) isPrime = false;
}
if (isPrime) {
result++;
prime[num] = i;
num++;
}
}
return result;
}
}
他山之石：
public class Solution {
public int countPrimes(int n) {
int result = 0;
boolean[] notPrime = new boolean[n];
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {
result ++;
for (int j = 2; j*i < n; j++) {
notPrime[j*i] = true;
}
}
}
return result;
}
}
這里其實(shí)還是那個(gè)思路，但是加快了速度苔悦，為什么呢轩褐？因?yàn)橹恍枰诿看斡龅劫|(zhì)數(shù)時(shí)，將其小于n的倍數(shù)都設(shè)為非質(zhì)數(shù)玖详，這樣就避免了每次遇到一個(gè)數(shù)都要用之前所有質(zhì)數(shù)去除一遍把介，大大降低了時(shí)間復(fù)雜度。
合集：https://github.com/Cloudox/LeetCode-Record
