质数筛

模板

将100000 以内的质数存入到数组prime当中

升级的模板多了 int L，是为了节省一些没有必要的循环，这是由质数的性质决定的 循环的范围只要是sqrt(L)就ok了

bool prime[100005];
void ai(int L) {
for (int i = 2; i <= 100000; ++i) prime[i] = 1;
int n = sqrt(L);
for (int i = 2; i <= n; ++i) {
if(prime[i]) {
for (int j = i*2; j <= L; j += i) {
prime[j] = 0;
}
}
}
}

这个是通过bool类型进行区分质数和非质数 所以使用的时候是通过if（prime[i]） 来进行操作来使用质数

例题是P5723 【深基4.例13】质数口袋 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Code

#include <bits/stdc++.h>
using namespace std;
bool prime[100005];
void ai(int L) {
for (int i = 2; i <= 100000; ++i) prime[i] = 1;
int n = sqrt(L);
for (int i = 2; i <= n; ++i) {
if(prime[i]) {
for (int j = i*2; j <= L; j += i) {
prime[j] = 0;
}
}
}
}
int main(){
int L,cnt=0;
cin >> L;
int p = L;
ai(L);
for (int i = 1; i <= p; ++i) {
if(prime[i]){
cout << i << endl;
p -= i;
cnt++;
}
if(p <= 0) break;
}
cout << cnt << endl;
return 0;
}

最后

以上就是文艺雪碧为你收集整理的质数筛（学习笔记）质数筛的全部内容，希望文章能够帮你解决质数筛（学习笔记）质数筛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。