204. 计数质数

2020-02-09

1.题目描述

输出小于非负整数n的所有质数

2.解答

最容易想到的一种方法，直接进行判断即可，超时： #include <iostream> using namespace std;class Solution { public:int countPrimes(int n) {int i,j,cnt=0;for (i=2;i<n;i++){for (j=2;j<i;j++){if (i%j==0) break;}if (j>=i) cnt++; }return cnt;} };int main(){Solution s;cout<<s.countPrimes(10)<<endl;return 0; } 考虑用素数筛的方法，注意在这里是如何进行内存分配的即可。

3.代码

#include <iostream> #include <cstring> using namespace std;class Solution { public:int countPrimes(int n) {bool *f = new bool[n];memset(f,0,sizeof(bool)*n);for (int i=2;i*i<n;i++){if (!f[i]){for (int j=i*i;j<n;j+=i){f[j]=true;}} }int cnt=0;for (int i=2;i<n;i++){if (!f[i]) cnt++;}delete[] f;return cnt;} };int main(){Solution s;cout<<s.countPrimes(499979)<<endl;return 0; }

总结

以上是生活随笔为你收集整理的204. 计数质数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。