085王子 - 数论入门作业1 - 快速求质数 - RE
public
Apr 07, 2025
Never
32
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 }