PAT乙级1013 || 数素数（详解，C/C++示例，测试点分析）

Posted on In

数素数

题目描述

令 P(i) 表示第 i 个素数。现任给两个正整数 M≤N≤$10^4$，请输出 P(M)到 P(N)的所有素数。

输入格式

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

输出格式

输出从P(M)到P(N)的所有素数，每 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

问题解决

解题思想

此题的关键在于输出格式的控制。单独设置一个变量j记录刚输出的素数是已输出素数的第几个，当j是10的倍数时（即j可以被10整除）输出换行。设置一个变量s来控制同一行各数之间的空格问题，这一方式在之前的题目中很常见，对于本题，注意每次换行时s应重置一下。还有一点要提醒大家，我一开始在main()函数中的for循环外添加了一行

1
printf("\n");

导致代码评测时有一个测试点没有通过，删去后全部通过。本人分析应为：若最后一行若恰好输出10个整数会导致重复换行问题，如果大家有确定的原因，欢迎大家留言指正，谢谢！

代码示例（C）

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <math.h>
int IsPrime(int t);

int main()
{
    int m,n,i,count = 0,j = 0,s = 0;
    //count记录当前为第几个素数
    //j记录已经输出的素数的个数
    //s控制输出格式，每次换行时s都要更新为0
    scanf("%d%d",&m,&n);
    for(i = 2; count <= n; i++){
        if(IsPrime(i)){
            count++;
            if((count >= m)&&(count <= n)){
                if(s == 0){
                    printf("%d",i);
                    s = 1;
                }
                else{
                    printf(" %d",i);
                }
                j++;
                if(j % 10 == 0){
                    printf("\n");
                    s = 0;//s重新更新为0
                }
            }
        }
    }
    return 0;
}
//判断t是否为素数，是素数则返回1，否则返回0
int IsPrime(int t)
{
    int i,flag = 0;
    for(i = 2; i <= sqrt(t); i++){
        if(t % i == 0){
            flag = 1;
            break;
        }
    }
    if(flag == 0){
        return 1;
    }
    else{
        return 0;
    }
}

题目来源：PAT乙级1013
作者：CHEN, Yue
单位：浙江大学

稀罕作者