B1013. 数素数 (20')

令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

解题思路：

可以根据N的上限去实际打印出第N个素数有多大也可以取一个比较大的数作为上限。这样，只要把第1~N个素数存在一个数组里（俗称打表），就可以通过一个循环直接打印出第M~N的素数。PS：在遍历循环到上限时应该在i遍历到达N时就中断循环，否则会运行超时。还有行末的空格也得需要注意一下。

#include <cstdio> #include <cmath> int a[999999]; //设置一个比较大的数组 int m, n; //判断是否是素数 bool isPrime(int n) { if(n == 1) return false; int sqr = (int)sqrt(1.0 * n); for(int i = 2; i <= sqr; i++) { if(n % i == 0) return false; } return true; } //打表，将前N个素数存入数组 void findPrime() { int cnt = 1; //统计个数 for(int i = 1; i <= 999999; i++) { if(isPrime(i)) a[cnt++] = i; //是素数，存入数组 if(cnt > n) break; } } int main() { int p = 1; //控制每10个换行的格式 scanf("%d %d", &m, &n); findPrime(); //打表 //打印第m~n个素数 for(int i = m; i <= n; i++) { printf("%d", a[i]); if(p % 10 != 0 && i < n) printf(" "); //p不到10的倍数且不是最后一个输出空格 else printf("\n"); p++; } return 0; }