用花生壳怎么做网站的服务器,房屋设计图怎么制作,沧州网站建设联系电话,温岭做网站给定整数 n #xff0c;返回 所有小于非负整数 n 的质数的数量 。 示例 1#xff1a;
输入#xff1a;n 10
输出#xff1a;4
解释#xff1a;小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。示例 2#xff1a;
输入#xff1a;n 0
输出#xff1a;0示例 3#…给定整数 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[n1]; 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;
}
};
分析
本题求素数的问题可以使用经典的埃氏筛法来解决埃氏筛法的原理即将每个找到的素数在所求范围中筛去非素数最后剩下的数即为所有此范围内的素数可以先创建一个数组将每个遍历到的素数记录下来筛去非素数并计数最后返回答案即可
总结
本题考察素数解法利用埃氏筛法可快速计数出答案
