PAT Basic 1013 数素数

题目

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

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

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

输入样例：

5 27

输出样例：

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

 

思路

1. 难点在于处理这个换行和空格的问题上面，要处理的情况有三种：

• 每行第一个数前面没有空格；
• 每行其他数前面带空格；
• 每行每10个数换行

刚开始的思路是每行最后一个换行。后来想想，第1行的最后一个后面加\n和第二行的第一个面前加\n是一样的，能不能将三种情况集合起来，一次性检测：

第1行第1个： cnt_p - M == 0 -> 什么也不做
其他行第一个：(cnt_p - M) % 10 == 0 && cnt_p - M != 0 -> 换行
其他数：前面加空格

2. 检测素数的函数有更快的，但是我记得的只有这个，以后有时间再补上。

 

代码

#include<stdio.h>
int isPrime(int num);

int main()
{
    int M = 0, N = 0;
    int cnt_p = 0; // 检测是第几个素数

    if(scanf("%d %d", &M, &N)){};

    for(int i = 2; cnt_p < N; i ++)
    {
        if(isPrime(i))
        {
            cnt_p++;
            if(cnt_p >= M) // 从第M个素数开始打印
            {
                if(cnt_p - M == 0)              {}
                else if((cnt_p - M) % 10 == 0)  {printf("\n");}
                else                            {printf(" ");}
                printf("%d", i);                
            }
        }
    }

    return 0;
}

// 检测是否是素数的函数
int isPrime(int num)
{
    int ret = 1;
    for(int i = 2; i * i <= num; i++)
    {
        if(num % i == 0) 
        {
            ret = 0; 
            break;
        }   
    }   
    return ret;
}