一.解法
https://leetcode-cn.com/problems/count-primes/
要點(diǎn)：埃拉托色尼篩選法
Python，C++迷捧，Java都用了相同的埃拉托色尼篩選法轻掩。
一開(kāi)始采用寫(xiě)一個(gè)isPrime函數(shù)判斷一個(gè)數(shù)是不是素?cái)?shù)幸乒，然后遍歷2到n-1計(jì)算個(gè)數(shù)的方法，結(jié)果超時(shí)唇牧。
于是學(xué)習(xí)了埃拉托色尼篩選法來(lái)計(jì)算質(zhì)數(shù)罕扎，這個(gè)方法類(lèi)似一種排除法，因?yàn)橐粋€(gè)合數(shù)總是可以分解成若干個(gè)質(zhì)數(shù)的乘積丐重，所以如果把質(zhì)數(shù)（最初只知道2是質(zhì)數(shù)）的倍數(shù)都去掉腔召，那么剩下的就是質(zhì)數(shù)了。
首先從 2 開(kāi)始扮惦，我們知道 2 是一個(gè)素?cái)?shù)臀蛛，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8... 都不可能是素?cái)?shù)了。
然后我們發(fā)現(xiàn) 3 也是素?cái)?shù)崖蜜，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12... 也都不可能是素?cái)?shù)了浊仆。
以此類(lèi)推得到答案，注意代碼中有兩個(gè)優(yōu)化的點(diǎn)豫领，第一個(gè)點(diǎn)是由于因子的對(duì)稱(chēng)性抡柿，，外層的 for 循環(huán)只需要遍歷 [2,sqrt(n)] 就夠了氏堤，第二個(gè)點(diǎn)是內(nèi)層的for循環(huán)可以寫(xiě)成for (int j = i * i; j < n; j += i)沙绝，因?yàn)楸热?n = 25搏明，i = 4 時(shí)算法會(huì)標(biāo)記 4 × 2 = 8，4 × 3 = 12 等等數(shù)字闪檬，但是這兩個(gè)數(shù)字已經(jīng)被 i = 2 和 i = 3 的 2 × 4 和 3 × 4 標(biāo)記了星著，會(huì)有重復(fù)標(biāo)記的地方。
二.Python實(shí)現(xiàn)
class Solution:
def countPrimes(self, n: int) -> int:
ans = [True] * n
count = 0
for i in range(2, int(n**0.5)+1):
if ans[i]:
for j in range(i*i, n, i):
ans[j] = False
for k in range(2, n):
if ans[k]:
count+=1
return count
三.C++實(shí)現(xiàn)
class Solution {
public:
int countPrimes(int n) {
if(n==0||n==1||n==2) return 0;
vector<bool> ans;
int count=0;
for(int i=0;i<n;i++){
ans.push_back(true);
}
for(int i=2;i*i<n;i++){
if(ans[i]){
for(int j=i*i;j<n;j=j+i){
ans[j]=false;
}
}
}
for(int i=2;i<n;i++){
if(ans[i]) count++;
}
return count;
}
};
四.java實(shí)現(xiàn)
class Solution {
public int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
Arrays.fill(isPrim, true);
for (int i = 2; i * i < n; i++)
if (isPrim[i])
for (int j = i * i; j < n; j += i)
isPrim[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim[i]) count++;
return count;
}
}
