題目在 https://zerojudge.tw/ShowProblem?problemid=a626
這題是要印出小於或等於n以內的所有質數. 求質數的方法可以參考我的另一篇 zerojudge b513. 判斷質數-商競103. 這題各位可能會錯在題目沒說測資中會有好幾個N,輸入為EOF代表測資結束,不同的N的答案要用’\n’分開. 這些都注意到,就會AC了.
程式跟上面提到的另一篇差不多, 我就不再解釋了. 完整程式如下.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
//V儲存所有的質數
vector <int> V;
//測試v是否為質數, 如果是就放入V中
void getNextPrime(int v){
int max=sqrt(v);
for(int i : V){
if(i>max) break;
if(v%i==0)
return;
}
V.push_back(v);
}
int main(){
//求出小於等於1000的所有質數
int n=1000;
V.push_back(2);
V.push_back(3);
int index=6;
while(index-1<=n){
getNextPrime(index-1);
if(index+1<=n){
getNextPrime(index+1);
}
index+=6;
}
//依測資要求印出所有質數
while(scanf("%d",&n)!=EOF)
{
int count=0;
for(int i : V){
if(i>n)
break;
printf("%10d",i);
//每印五個數要換行
count++;
if(count%5==0)
printf("\n");
}
//換印下一題前要先換行, 如果已經印過\n就不再換行
if(count%5)
printf("\n");
}
}