084黄弈铖 - 数论入门随堂练习1 - 快速求质数
public
Apr 06, 2025
Never
37
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