LeetCode 204. Count Primes计数质数 (C++)
2024-09-01 12:38:18
题目:
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
分析:
统计所有小于非负整数 n 的质数的数量。
这里使用埃拉托斯特尼筛法。要得到自然数n以内的全部素数,必须把不大于√n的所有素数的倍数剔除,剩下的就是素数。
例如我们要求2-25以内素数的个数,
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
第一次先剔除掉2以后的倍数
2,3,5,7,9,11,13,15,17,19,21,23,25
接下来剔除3的倍数
2,3,5,7,11,13,17,19,23,25
接下来剔除5的倍数
2,3,5,7,11,13,17,19,23
由于7 > √25,算法停止。
我们可以初始化大小为n的数组res,其内所有元素均为1,默认所有数字均为素数,首先将0,1剔除掉,然后开始执行算法,当前元素i,若res[i]==1,将i的倍数全部置为0,若res[i]==0,则继续执行,注意本题是求小于n的素数的个数,终止条件设为小于sqrt(n)即可,若包括n,则需要小于等于sqrt(n)。
程序:
class Solution {
public:
int countPrimes(int n) {
if(n < ) return ;
vector<int> res(n, );
res[] = ;
res[] = ;
for(int i = ; i < sqrt(n); ++i){
if(res[i] != )
continue;
for(int j = i*; j < n; j += i){
res[j] = ;
}
}
int num = count(res.begin(), res.end(), );
return num;
}
};
最新文章
- AngularJS执行流程详解
- 使用Percona Toolkit解决Mysql主从不同步问题【备忘】
- json转换数据后面参数要带ture,代码
- vimium: 浏览器神器
- retrofit2 上传图片
- jqeury轮播
- Entity Framework菜鸟初飞
- mui中的关闭页面的几种方法
- jmeter做接口测试
- leetcode:Intersection of Two Linked Lists(两个链表的交叉点)
- Linux编程之《看门狗进程》
- [转贴]实践:C++平台迁移以及如何用C#做C++包装层
- 基于redis的cas集群配置(转)
- CSS Flexbox 学习指南、工具与框架
- Unity 工作经历+近期面试经历
- c语言 内存管理
- outline
- python学习:函数传参数
- Android Activity的四种经典传值方法
- Linux内核中断和异常分析(上)