质数筛（学习笔记）质数筛

92 阅读 0 评论 61 点赞

我是靠谱客的博主文艺雪碧，这篇文章主要介绍质数筛（学习笔记）质数筛，现在分享给大家，希望可以做个参考。

质数筛

模板

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}