G

084黄弈铖 - 数论入门随堂练习1 - 快速求质数

public
Guest Apr 06, 2025 Never 37
Clone
C++ 084黄弈铖 - 数论入门随堂练习1 - 快速求质数 45 lines (41 loc) | 1.11 KB
1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N = 2e5+5;
4
int n,m,primes[N],cnt;
5
6
// 256M = 256 * 1024 * 1024 B ~ 2e8
7
// INT_MAX = 21 4748 3647 ~ 2e9
8
//bool vis[INT_MAX];
9
bool vis[N];
10
11
int main()
12
{
13
cin>>n>>m;
14
// for(int i=2;i<=n;i++) // n 最大为 INT_MAX,筛至平方根以上就够了
15
for(int i=2;i<N;i++)
16
{
17
if(!vis[i]) primes[cnt++]=i;
18
// for(int j=0;primes[j]<=n/i;j++)
19
for(int j=0;primes[j]<N/i;j++)
20
{
21
// vis[primes[j*i]]=true; // 写错了
22
vis[primes[j]*i] = true;
23
if(i%primes[j]==0) break;
24
}
25
}
26
27
// for(int i=1;i<=cnt;i++) if(primes[i]>=n) cout<<primes[i]<<" ";
28
for(long long i=n;i<=m;i++) { // m 最大值为 (1<<31)-1 即 INT_MAX,不存在更大的 整型数
29
bool is_prime = true;
30
if(i<2) is_prime = false; // 1 要特判
31
for(int j=0;(long long)primes[j]*primes[j]<=i;j++) { // primes[j] * primes[j] 同理
32
if(i%primes[j]==0) {
33
is_prime = false;
34
break;
35
}
36
}
37
if(is_prime) cout << i << " ";
38
}
39
return 0;
40
}
41
42
/*
43
2147482647
44
2147483647
45
*/
46