G

085王子 - 数论入门作业1 - 快速求质数 - RE

public
Guest Apr 07, 2025 Never 32
Clone
Plaintext 085王子 - 数论入门作业1 - 快速求质数 - RE 48 lines (45 loc) | 1.22 KB
1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N = 1e5+5;
4
5
int n,m;
6
vector<int> vec;
7
vector<int> prime, notPrime(N);
8
9
// 线性筛法,O(N) 得到所有质数
10
void Euler() {
11
for(int i=2; i<N; i++) {
12
if(!notPrime[i])
13
prime.push_back(i);
14
for(int j=0; j<prime.size() && i*prime[j] < N; j++) {
15
notPrime[i*prime[j]] = 1;
16
if(i % prime[j] == 0)
17
break;
18
}
19
}
20
}
21
22
int main() {
23
cin>>n>>m;
24
Euler();
25
// if(n<=2&&m>=2)vec.push_back(2);
26
for(long long i=n; i<=m; i++) { // m 最大值为 INT_MAX, 如果 i 为 int类型, i<=m 永远成立
27
bool b=true;
28
if(i==1)b=false;
29
// if(i%3==0&&i>3)b=false;
30
// if(i%5==0&&i>5)b=false;
31
for(int j=0; j<prime.size() && (long long)prime[j]*prime[j]<=i; j++) // 遍历所有质数
32
if(i%prime[j]==0) { // 如果 i 存在 质因数, 则 i 不是 质数
33
b = false;
34
break;
35
}
36
// for(int j=3;j*j<=i&&b;j+=2){
37
// if(i%j==0){b=false;break;}
38
// }
39
if(b) {
40
vec.push_back(i);
41
}
42
}
43
for(int i=0; i<(int)vec.size()-1; i++) { // vec.size() 的返回值 是一个 无符号 类型, 0 减 1 会得到 容器数据类型的最大值
44
cout<<vec[i]<<' ';
45
}
46
if(vec.size()!=0)cout<<vec[vec.size()-1]<<endl;
47
return 0;
48
}