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

Ranbo_

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

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <math.h>
   
4. 
   
5. int is_prime(int n)
   
6. {
   
7.     if(n == 2)
   
8.         return 1;
   
9.     for(int i = 2; i <= sqrt(n); i++)
   
10.     {
    
11.         if(n % i == 0)
    
12.             return 0;
    
13.     }
    
14.     return 1;
    
15. }
    
16. 
    
17. int main()
    
18. {
    
19.     int m, n;
    
20.     scanf("%d %d", &m, &n);
    
21.     int count = 0;//count记录素数的个数
    
22.     int sum = 0;//sum记录输出了的素数的个数
    
23.     int num = 2;//num从2开始一直自增
    
24.     int i;
    
25.     while(count != m)
    
26.     {
    
27.         if(is_prime(num))
    
28.             count++;
    
29.         num++;
    
30.     }
    
31.     //此时num-1为第m个素数
    
32.     if(m == n)
    
33.         printf("%d\n", num-1);
    
34.     else
    
35.         printf("%d ", num-1);
    
36.     sum = 1;
    
37.     while(count != n)
    
38.     {
    
39.         if(is_prime(num))
    
40.         {
    
41.             sum++;count++;
    
42.             if((sum % 10 == 0) || count == n)
    
43.                 printf("%d\n", num);
    
44.             else
    
45.                 printf("%d ", num);
    
46.         }
    
47.         num++;
    
48.     }
    
49. }
    

复制代码

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