力扣-204 計數質數
這題用普通的質數篩選方法直接就給你超時了,所以我們肯定得用其他的方法,對算法進行改進
思路就是,先定義一個數組進行標記。
開始定義這個數組所表示的數全部都是質數,然后開始篩選。
假如這個數是質數,那么這個數的倍數就全部都被篩選下來了。
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篩去。
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;}
};
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态