彩笔
2022-10-03

线性筛素数

【模板】线性筛素数 - 洛谷

【深基7.例2】质数筛 - 洛谷

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <bitset>
typedef long long ll;
const int sz=1e8+10;

namespace sscio {
inline ll pull() {
ll sign = 1LL,res = 0LL;
char ch = getchar();
for (;!isdigit(ch);ch=getchar()) {
if (ch == '-') {
sign *= -1LL;
}
}
for (;isdigit(ch);ch = getchar()) {
res = (res << 3) + (res << 1) - '0' + ch; // *10
}
return sign * res;
}
}

using std::bitset;
bitset<sz> primeTable;
int primes[sz],prpp=0;
void fetchPrimes(const int &ed) { //线性筛 形参为边界
primeTable.reset();
primeTable.set(0);
primeTable.set(1);
for(register int cx=2;cx<ed;cx++) {
if(!primeTable[cx]) {
primes[prpp++]=cx;
}
for (register int cy=0;cy<prpp&&cx*primes[cy]<ed;cy++) { //用质数来筛质数
primeTable.set(cx*primes[cy]);
if (cx%primes[cy]==0) {
break;
}
}
}
}

void solve() {
fetchPrimes(sz-6);
int n=sscio::pull(); //n为查询范围,因为已经筛了超出题目范围素数了,所以无需处理
int p=sscio::pull(); //查询的个数
while(p--) {
int k=sscio::pull(); //表示查询第 k 小的素数
printf("%d\n", primes[k-1]); //因为我们下标从零开始 所以是k - 1
}
}

signed main() {
solve();
return 0 ^ 0;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <bitset>
typedef long long ll;
const int sz=1e5+10;

namespace sscio {
inline ll pull() {
ll sign = 1LL,res = 0LL;
char ch = getchar();
for (;!isdigit(ch);ch=getchar()) {
if (ch == '-') {
sign *= -1LL;
}
}
for (;isdigit(ch);ch = getchar()) {
res = (res << 3) + (res << 1) - '0' + ch; // *10
}
return sign * res;
}
}

using std::bitset;
bitset<sz> primeTable;
int primes[sz],prpp=0;
void fetchPrimes(const int &ed) { //线性筛 形参为边界
primeTable.reset();
primeTable.set(0);
primeTable.set(1);
for(register int cx=2;cx<ed;cx++) {
if(!primeTable[cx]) {
primes[prpp++]=cx;
}
for (register int cy=0;cy<prpp&&cx*primes[cy]<ed;cy++) { //用质数来筛质数
primeTable.set(cx*primes[cy]);
if (cx%primes[cy]==0) {
break;
}
}
}
}

void solve() {
fetchPrimes(sz-6);
// int n=sscio::pull(); //n为查询范围,因为已经筛了超出题目范围素数了,所以无需处理
int p=sscio::pull(); //查询的个数
int cnt = 0; //空格数量
while(p--) {
int k=sscio::pull();
if (!primeTable[k]) {
if (cnt==0) {
cnt++;
} else {
putchar(' ');
}
printf("%d", k);
}
}
}

signed main() {
solve();
return 0 ^ 0;
}