Lipsky

PAT 1013 数素数

字数统计: 393阅读时长: 1 min
2019/03/21 Share

PAT 1013 数素数 (20分)#

令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤104,请输出 PM 到 PN 的所有素数。

输入格式:#

输入在一行中给出 M 和 N,其间以空格分隔。

输出格式:#

输出从 PM 到 PN 的所有素数,每 10 个数字占 1 行,其间以空格分隔,但行末不得有多余空格。

输入样例:#

1
5 27

输出样例:#

1
2
3
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

分析:#

可以用 vector 容器来存储所有第 M 个 到 第 N 个素数,然后,再输出。

输入问题,判断从第 M 个素数开始,才写入 vector 容器中,第 M 个之前的都不写入。再设置一个参数 cnt ,每次写入之后加 1, 到第 N 个停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<vector>
using namespace std;
bool isprime(int a) {
for (int i = 2; i * i <= a; i++)
if(a % i == 0) return false;
return true;
}

int main(){
int M, N, num = 2, cnt = 0;
vector<int> v;
cin >> M >> N;
while(cnt < N){ //当素数个数小于最大的 N 时,继续写入 v 中
if( isprime(num)){
cnt++; //素数判断基数增加 1
if(cnt >= M) v.push_back(num); //如果这个素数是第 M+ 个素数(包括第 M 个),写入 v
}
num++; //总素数个数增加 1

}
cnt = 0;
for ( int i = 0; i < v.size(); i++){
cnt++;
if(cnt % 10 != 1) printf(" ");
printf("%d", v[i]);
if(cnt % 10 == 0) printf("\n");
}

return 0;
}
CATALOG
  1. 1. PAT 1013 数素数 (20分)#
    1. 1.1. 输入格式:#
    2. 1.2. 输出格式:#
    3. 1.3. 输入样例:#
    4. 1.4. 输出样例:#
    5. 1.5. 分析:#