力扣-204 計數質數

這題用普通的質數篩選方法直接就給你超時了，所以我們肯定得用其他的方法，對算法進行改進

埃式篩

思路就是，先定義一個數組進行標記。
開始定義這個數組所表示的數全部都是質數，然后開始篩選。
假如這個數是質數，那么這個數的倍數就全部都被篩選下來了。

AC Code

class Solution {
public:bool ret[10000006];int countPrimes(int n) {int ans =0;if(n<2) return 0;for(int i=2;i<n;i++){if(!ret[i]){for(int j = 2;j*i<n;j++)ret[j*i]=1;ans++;}}return ans;}
};

線性篩

線性篩的核心思想：每個合數只會被自己的最小的質因數篩去。
比如：12只會被2篩去 21只會被3篩去。

AC Code

class Solution {
public:int ret[10000006];int prime[1000005];int countPrimes(int n) {if(n<2) return 0;ret[0]=ret[1]=1;int cnt=0;for(int i=2;i<n;i++){if(!ret[i]){prime[cnt++]=i;}for(int j=0;j<cnt && i*prime[j]<n;j++){ret[i*prime[j]] = 1;if(i%prime[j] == 0) break;}}return cnt;}
};