Leetcode 204. 计数质数 解题思路及C++实现

解题思路：

利用一个数组记录 n 个数是否为质数。

质数的倍数都是非质数，就这样遍历下去就可以了。

 

class Solution { public:int countPrimes(int n) {if(n < 3) return 0;int res = 0;vector<bool> tag(n, true); //先初始化所有的数都是质数for(int i = 2; i < n; i++){if(tag[i]){ //当前数字是质数for(int j = 2*i; j < n; j+=i){ //质数的所有倍数对应的都是非质数tag[j] = false;}res++; //每当有一个质数，就将结果加1}}return res;} };

 

 

 

 

总结

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

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