204. 计数质数-暴力解法和埃氏筛
解法 暴力 计数 质数
2023-09-14 09:06:49 时间
204. 计数质数-暴力解法和埃氏筛
给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。
示例 1:
输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:
输入:n = 0
输出:0
示例 3:
输入:n = 1
输出:0
暴力解法呢,时间上应该是通过不了,解题代码如下:
bool isPrime(int x) {
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
int countPrimes(int n) {
int ans = 0;
for (int i = 2; i < n; ++i) {
ans += isPrime(i);
}
return ans;
}
埃氏筛是空间换时间的做法,解题代码如下:
int countPrimes(int n){
int sum=0;
if(n==0){
return 0;
}
int r[n];
for(int i=2;i<n;i++){
r[i]=0;
}
for(int i=2;i<n;i++){
if(r[i]==0){
sum++;
for(int j=2*i;j<n;j=j+i){
r[j]=1;
}
}
}
return sum;
}
相关文章
- 指派问题与匈牙利解法
- 蓝桥杯(Java方法、详细解法分析)基础练习 阶乘计算
- 蓝桥杯 算法训练 P0505(Java解法)
- Leetcode0001: 两数之和(simple, 4种解法)
- Leetcode688: 骑士在棋盘上的概率(medium, 基于概率转移矩阵的解法)
- 【a703】求逆序对(树状数组的解法)
- 蓝桥杯官网 试题 PREV-94 历届真题 矩阵计数【第十届】【决赛】【研究生组】【C++】解法
- 蓝桥杯官网 试题 PREV-109 历届真题 扫地机器人【第十届】【省赛】【研究生组】【C++】【Java】【Python】三种解法
- 蓝桥杯官网 试题 PREV-281 历届真题 时间显示【第十二届】【省赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 2195. 向数组中追加 K 个整数-快速排序暴力解法+优化解法
- 面试题 16.05. 阶乘尾数-暴力解法和优化算法
- 560. 和为 K 的子数组-前缀和+暴力解法和前缀和+哈希表解法
- 面试题 16.21. 交换和-哈希表解法
- 【数字信号处理】线性常系数差分方程 ( 概念 | 线性常系数差分方程解法 )
- Sort List[leetcode] 由归并排序的递归和循环,到本题的两种解法
- FizzBuzzWhizz问题python解法
- C# 汉诺塔(Hanoi)的递归解法
- 【笔试题】需要和题目紧密相连的解法