当前位置:首页 > 编程笔记 > 正文
已解决

leetcode做题笔记204. 计数质数

来自网友在路上 185885提问 提问时间:2023-10-28 04:22:42阅读次数: 85

最佳答案 问答题库858位专家为你答疑解惑

给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。

示例 1:

输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2:

输入:n = 0
输出:0

示例 3:

输入:n = 1
输出:0

思路一:埃式筛法

c++解法

class Solution {
public:int countPrimes(int n)
{int a[n+1]; int count = 0;for(int i = 2; i < n; i++)a[i] = 1;for(int i = 2; i < n; i++)if(a[i]){count++;for(int j = 2 * i; j < n; j += i)a[j] = 0;}return count;
}
};

分析:

本题求素数的问题,可以使用经典的埃氏筛法来解决,埃氏筛法的原理即将每个找到的素数在所求范围中筛去非素数,最后剩下的数即为所有此范围内的素数,可以先创建一个数组将每个遍历到的素数记录下来,筛去非素数并计数,最后返回答案即可

总结:

本题考察素数解法,利用埃氏筛法可快速计数出答案

查看全文

99%的人还看了

猜你感兴趣

版权申明

本文"leetcode做题笔记204. 计数质数":http://eshow365.cn/6-26551-0.html 内容来自互联网,请自行判断内容的正确性。如有侵权请联系我们,立即删除!