PAT Basic 1013. 数素数 (20)（C语言实现）

我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。

题目

令 表示第 个素数。现任给两个正整数 ，请输出 到 的所有素数。

输入格式：

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

输出格式：

输出从 到 的所有素数，每 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

思路

也没有什么难度，注意下什么时候开始输出，什么时候换行。

和1007. 素数对猜想 (20) （C语言实现）一样，验证素数的时候，利用前面已经算出的素数，能够将验证次数降到最低。

代码

最新代码@github，欢迎交流

#include <stdio.h>

int main()
{

    int M, N;
    scanf("%d %d", &M, &N);
    int primes[10000];

    for(int n = 2, count = 0; count < N; n++)
    {
        /* Check if n is prime number */
        int iprime = 1;
        for(int j = 0; count > 0 && primes[j] * primes[j] <= n; j++)
            if(n % primes[j] == 0)
                iprime = 0;

        /* Record */
        if(iprime)
            primes[count++] = n;
    }

    /* Print */
    for(int i = M; i < N; i++)
    {
        printf("%d", primes[i - 1]);
        printf((i - M + 1) % 10 ? " " : "\n");
    }
    printf("%d", primes[N - 1]);

    return 0;
}