LeetCode204:Count Primes
2024-10-16 17:52:45
Description:
Count the number of prime numbers less than a non-negative number, n.
比计算少n中素数的个数。
素数又称质数,是指仅仅能被1和它自身相除的自然数。
须要注意的是1既不是素数也不是合数。
2是最小的素数。
使用推断一个数是否是素数的函数,那么这个函数须要进行一轮循环,在给定的小于n中又要进行一轮循环。所以时间复杂度是O(n^2)。
能够对推断一个数是否是素数的函数进行优化。对于数i,能够仅仅对2到√i之间的数进行推断。这样时间复杂度减少到了O(nlogn)。
可是上面的解法在leetcode中还是超时。
于是想是否存在仅仅进行一轮循环的方法。即在遍历1至n-1一次的过程中记录下素数的个数。可是后面就不知道怎么处理。
然后看leetcode中的小提示,发现了一种更优的寻找素数的方法。首先看以下的这个图:
这个图事实上就道出了这个算法是怎么进行的。使用一个长度是n的hash表,最開始这个hash表中的全部元素都是没有被处理的,从2開始遍历,假设这个元素没有被处理,那么将素数的个数加1,然后将2*2,2*3,2*4……2* k( 2* k < n)标记为已经被处理了的。接着開始处理3,同理将3*2,3*3,3*4…..3*m( 3 * m < n)标记为已被处理了的,接着是4,因为这个元素已经被处理。继续向后遍历。这样一直处理下去。
从这道题中又意识到了一个整数会溢出会导致问题的小技巧。
两种解法分别例如以下:
class Solution {
public:
/*
//解法一:超时
int countPrimes(int n) {
int count=0;
for(int i=2;i<=n;i++)
{
if(isPrime(i))
count++;
}
return count;
}
bool isPrime(int n)
{
if(n==1)
return false;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
return false;
}
return true;
}
*/
//解法二:
int countPrimes(int n) {
int * mask=new int[n]();//能够在这里直接对动态数组进行初始化
int count=0;
for(int i=2;i<n;i++)
{
if(mask[i]==0)
{
count++;
for(int j=2;i*j<n;j++)//这里不能将j初始化成i,否则i*j会溢出
{
mask[i*j]=1;
}
}
}
return count;
}
};
版权声明:本文博主原创文章,博客,未经同意不得转载。
最新文章
- OPENVPN
- 条件随机场matlab程序下载
- Android退出时关闭所有Activity的方法
- Apache下开启SSI配置使html支持include包含
- CocoStudio教程三:认识并利用CocoStudio的果实 运行2.2.1版本
- Careercup - Facebook面试题 - 6321181669982208
- maven项目配置Project Facets时further configuration available不出来问题
- sql 将datetime类型转化为指定格式的字符串
- 关于使用JavaScript实现图片点击切换(附带改变导航图片 方案二)
- Red Hat
- iOS 10正式发布:十大新功能,更注重人性化
- CVTE前端一面
- Android BrocastReceiver解析
- LeetCode(111):二叉树的最小深度
- 生成缓存文件cache file
- 编译darknet出现libpng16.so.16:对‘inflateValidate@ZLIB_1.2.9’未定义的引用
- 排序算法练习--JAVA(:内部排序:插入、选择、冒泡、快速排序)
- [Noip2015PJ] 求和
- c#:HttpClient加标头
- 100 行代码实现的 JavaScript MVC 样式框架
热门文章
- 网络知识汇总(2) - Linux下如何修改ip地址
- JS跑马灯
- 辛星PHP教程之yii和ci教程已经写完,望与朋友们交流
- 实时人脸检测 (Real-Time Face Detection)
- 魔棒工具--RegionGrow算法简介
- 摘要算法CRC8、CRC16、CRC32,MD2 、MD4、MD5,SHA1、SHA256、SHA384、SHA512,RIPEMD、PANAMA、TIGER、ADLER32
- CreateThread、_beginthreadex和AfxBeginThread 的区别
- 从零开始,使用python快速开发web站点(2)
- Thrift搭建分布式微服务1
- cisco路由器IPSEC VPN配置(隧道模式)