https://pintia.cn/problem-sets/994805260223102976/problems/994805309963354112

樸素寫法

#include<cstdio> bool a[1000005]={false}; int b[10005]; int main(void) {int m,n;int i,j;for(i=2;i<=1000005;i++){ if(a[i]==false)for(j=i+i;j<=1000005;j=j+i){a[j]=true;}}j=0;for(i=2;i<=1000005;i++){if(a[i]==false){b[j++]=i;}}while( scanf("%d%d",&m,&n) != EOF ){int count=0;for(i=m-1;i<=n-1;i++){printf("%d",b[i]);count++;if(count<10&&i!=n-1){printf(" ");}if(count==10){printf("\n");count=0;}}if(count!=0)printf("\n"); }return 0; }

線性篩寫法

#include<cstdio> #include<iostream> using namespace std; int primes[20005],cnt; bool st[200005]; void print() {for(int i=2;i<=200000;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]<=200000/i;j++){st[primes[j]*i]=true;if(i%primes[j]==0) break;}} } int main(void) {int a,b; cin>>a>>b;print();int count=1;for(int i=a-1;i<b;i++){cout<<primes[i];if(count<10&& (i!=b-1)) cout<<" ";if(count%10==0) cout<<endl,count=0;count++;}return 0; } #include<cstdio> #include<iostream> #include<vector> using namespace std; const int N=1e4*2+10; int m,n; bool a[N]; vector<int> ans; void prime() {for(int i=2;i<N;i++){if(!a[i]){ans.push_back(i);for(int j=i;j<N;j+=i) a[j]=true;}} } int main(void) {cin>>m>>n;prime();int count=0;for(int i=m-1;i<n;i++) {count++;cout<<ans[i];if(count!=10) cout<<" ";else count=0;} }

總結(jié)

以上是生活随笔為你收集整理的【PAT乙级】1013 数素数 (20 分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。