乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT乙级BasicLevelPractice 1013

问题分析

题目给定了两个正整数M, N(M <= N), 要求输出从第M个素数开始, 到第N个素数结束的所有素数.
所以最直接的想法是, 如果我们有一个判断素数的方法,
从1开始判断, 同时设置计数器, 如果计数器加到了M就开始输出, 如果计数器加到了N就结束循环。
则: 我们的重点就是构造素数判断的方法了。
另一个重点是, 我们这么简单粗暴的方案是否会导致时间过长超出限制.
如果时间超出限制了, 就需要考虑增加逻辑跳过一些不需要判断的数(比如可以被2整除的数)。

关于素数的判断方法，我们在之前BasicLevel1007中已经提及，这里不再占用篇幅赘述了。

伪代码描述步骤

• 读入题设要求的两个正整数M, N
• 设置计数器count, 记录当前找到的素数是第几个素数
• for 从2开始的正数x:
  • 如果x是素数, 则计数器+1
  • 如果计数器大于等于M, 需要输出x
    • 如果输出的数目是10的倍数, 则需要换行
    • 如果输出的数目不是10的倍数, 且不是最后一个要求输出的素数, 则需要输出空格

完整提交代码

/*
# 问题分析
题目给定了两个正整数M, N(M <= N), 要求输出从第M个素数开始, 到第N个素数结束的所有素数.
所以最直接的想法是, 如果我们有一个判断素数的方法,
从1开始判断, 同时设置计数器, 如果计数器加到了M就开始输出, 如果计数器加到了N就结束循环。
则: 我们的重点就是构造素数判断的方法了。
另一个重点是, 我们这么简单粗暴的方案是否会导致时间过长超出限制.
如果时间超出限制了, 就需要考虑增加逻辑跳过一些不需要判断的数(比如可以被2整除的数)。

*/

#include 
#include 

int is_primary(int number)
{
    if (number == 2)
    {
        return 1;
    }

    int max_limit = (int)sqrt(number) + 1;
    for (int i = 2; i < max_limit; i++)
    {
        if (number % i == 0)
        {
            return 0;
        }
    }

    return 1;
}

int main()
{
    int M, N;
    scanf("%d %d", &M, &N);

    int amount = 0;
    for (int i = 2; amount < N; i++)
    {
        if (is_primary(i) == 0)
            continue;

        amount++;
        if (amount >= M)
        {
            printf("%d", i);
            if ((amount - M + 1) % 10 == 0)
            {
                printf("\n");
            }
            else if (amount < N)
            {
                printf(" ");
            }
        }
    }

    return 0;
}
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
50
51
52
53
54
55
56
57
58
59
60
61