概述
筛质数有两个板子，埃氏筛和欧拉筛，欧拉筛是线性的，背一个欧拉筛就够了
欧拉筛(线性筛)板子
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int prim[N]; //存储质数
bool vis[N]; //标记合数
int cnt; //总个数
int main(){
int n;
cin >> n;
for(int i = 2; i <= n; ++i){//质数从2开始遍历
if(!vis[i]) prim[cnt++] = i; //i不为合数时，放进质数数组
for(int j = 0;1ll*i*prim[j] <=n ; ++j){ //标记当前数i X 之前筛出来的质数 得到的合数
vis[i*prim[j]] = 1;
if(i%prim[j]==0) break; //整除中断
}
}
cout << cnt << endl;
return 0;
}
题目
| 题目 | 难度 |
|---|---|
| Acwing.筛质数 | 模板题 |
| 洛谷.【模板】线性筛素数 | 模板题 |
最后
以上就是独特火龙果为你收集整理的筛质数——欧拉筛(线性筛)欧拉筛(线性筛)板子题目的全部内容，希望文章能够帮你解决筛质数——欧拉筛(线性筛)欧拉筛(线性筛)板子题目所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复