输出第M到第N个素数的所有素数

Ranbo_

令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，输出PM到PN的所有素数。
要求：每10个数字占1行，其间以空格分隔，但行末不得有多余空格。

这是pat真题。因为我没学过算法，所以我的思路很简单，就是直接一个一个输入判断，为了防止运行时间超出限制，需要了解一点，即判断一个数n是否为素数，只需要看2~sqrt(n)以内的数是否为n的因数即可。时间复杂度应该是O(n^3/2)。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

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

int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    int count = 0;//count记录素数的个数
    int sum = 0;//sum记录输出了的素数的个数
    int num = 2;//num从2开始一直自增
    int i;
    while(count != m)
    {
        if(is_prime(num))
            count++;
        num++;
    }
    //此时num-1为第m个素数
    if(m == n)
        printf("%d\n", num-1);
    else
        printf("%d ", num-1);
    sum = 1;
    while(count != n)
    {
        if(is_prime(num))
        {
            sum++;count++;
            if((sum % 10 == 0) || count == n)
                printf("%d\n", num);
            else
                printf("%d ", num);
        }
        num++;
    }
}

这个题有一种其他做法：埃拉托斯特尼筛法 ------ 要得到自然数n以内的全部素数，必须把不大于sqrt(n)的所有素数的倍数剔除，剩下的就是素数。
实现：用一个长度为N+1的数组保存信息，先将数组所有元素初始化为0，从第一个素数2开始，把2的倍数都标记为非素数（置1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。但是这样需要大概了解第10000个素数的大小。