线性素数筛(欧拉筛)(超级好的MuBan)
2024-08-27 23:38:32
Problem:找出小于等于n的所有素数的个数。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int prime[maxn]; // 欧拉线性素数筛,O(n)
bool vis[maxn]; // 标记
int Prime(int n)
{
memset(vis,false,sizeof(vis));
int cnt = 0;
vis[0] = vis[1] = true;
for(int i = 2; i <= n; i ++)
{
if(!vis[i])prime[cnt++] = i;
for(int j = 0; j < cnt && i*prime[j] <= n; j ++)
{
vis[i*prime[j]] = true;
if(!(i%prime[j])) break;
}
}
return cnt;
}
int main()
{
int n;
cin >> n;
int ans = 0;
ans = Prime(n);
cout << ans << endl;
return 0;
}
if(i % prime[j] == 0) break;
解释:
首先,任何合数都能表示成多个素数的积。所以,任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。当i是prime[j]的整数倍时(i % prime[j] == 0),i*prime[j+1]肯定被筛过,跳出循环。
因为i可以看做prime[j]*某个数, i*prime[j+1]就可以看做 prime[j]*某个数*prime[j+1] 。而 prime[j] 必定小于 prime[j+1],
所以 i*prime[j+1] 必定已经被 prime[j]*某个数 筛掉,就不用再做了√同时我们可以发现在满足程序里的两个条件的时候,prime[j]必定是prime[j]*i的最小质因子。这个性质在某些题里可以用到。
这样就可以在线性时间内找到素数啦~\(≧▽≦)/~
解释转自https://blog.csdn.net/tianwei0822/article/details/78309453
最新文章
- Apache shiro 文章推荐
- 【性能诊断】五、并发场景的性能分析(windbg简介及dump抓取)
- CentOS 7下安装Mysql 5.7
- mysql日常语句总结
- Codeforces Round #377 (Div. 2)D(二分)
- echo
- Android IPC(inter-process Communitcation)
- 对象的继承关系在数据库中的实现方式和PowerDesigner设计
- Linux的/etc/issue、/etc/issue.net和/etc/motd的区别
- php 大数组的POST问题解决
- Centos中压缩(zip)和解压(unzip)命令
- git clone 带用户名密码的形式但包含@等特殊符号无法正常解析
- Javascript入门(一)弹出方框
- 【每日一题】 UVA - 11809 Floating-Point Numbers 阅读题+取对数处理爆double
- C#打印0到100的素数
- Pronunciation – The Definitive Guide to the Top 100 Words in American English
- 【Hibernate】hibernate框架的搭建
- SuperMap(无对应字段)空间属性挂接
- BZOJ 1051 受欢迎的牛 缩点
- bzoj 4319 cerc2008 Suffix reconstruction——贪心构造