万人千题——素数筛选
2023-02-18 16:26:26 时间
一个题用英雄哥博客中写的方法就能解决,所以说完成起来还是比较简单的。 计数质数
bool f[50001];
#define ll long long;
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)
{
int ans = 0;
for (int i = 2; i < n; ++i)
{
ans += isPrime(i);
}
}
return ans;
}
暴力解法,看图吧
还是要优化,首先分析为什么超时,发现主要的原因是从2开始每一个数都进行了素数的判断,所以说浪费了时间,在上一篇素数的判断,我们提到可以使素数*相同的倍数,来减少判断的次数。 从而引出了Eratosthenes筛选
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
bool f[50001];
int countPrimes(int n)
{
int i;
int cnt = 0;
ll j;
f[0] = f[1] = 1;
for (i = 2; i < n; ++i)
{
if (!f[i])
{
++cnt;
for (j = (ll)i*i; j < n; j += i)
{
f[j] = 1;
}
}
}
return cnt;
}
int main()
{
cout<<countPrimes(10);
return 0;
}
看似俩个for循环,虽然有两个嵌套的轮询,但是第二一个轮询只有在i是素数的时候才会执行,而且随着i的增大,它的倍数会越来越少,所以整个算法的时间复杂度并不是O(n2),且远远小于O(n2)。 从而实现了时间的减少,
相关文章
- 当expandlistview的getGroupView或者getChildView中包含checkbox时,前者点击不可用
- 1.怎样徒手写一个React
- SaaS是什么?企业采购SaaS有什么好处?
- java处理保留小数点后几位
- String、StringBuffer、StringBuilder的区别
- ScrollView嵌套listview、gradview等 嵌套时显示问题的解决办法
- 严守看门人职责,抖音用科技让世界杯更安全
- 优思学院|六西格玛管理六步法的迷思和正解
- 如何制作gif图片?如何制作你项目的动态效果图到你的csdn?
- 高可用架构和系统设计经验
- 我终于统一了团队的技术方案设计模板
- SVN提示locked解决办法
- Edittext In Listview,当listview的item中有edittext时,怎么保存edittext的值?
- setOnTouchListener使用记录
- 异常的出现情况及解决方式(持续更新中)
- xUtils 的 post和get 请求 使用记录
- 在代码修改textview的Drawable 和 使用webview 加载网页
- 修改魅族和小米状态栏的文字颜色
- 自定义View实战(一) 汽车速度仪表盘
- 自定义View实战(二)QQ健康水滴形加载