传送门
https://pintia.cn/problem-sets/994805260223102976/problems/994805309963354112
题目
令Pi表示第i个素数。现任给两个正整数M <= N <= 104，请输出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
分析
此题困扰了时间还蛮长的，主要就是效率问题，要在100ms内求出第10000个以内的素数，这与求10000以内的素数的计算次数完全不同。我是在参考了别人的代码后才写出来的，还考虑了好久算法的问题，发现了一个规律：一个数，只要它不是素数（质数），那么它肯定至少有一个因子是素数。这个规律我没法去证明，但是还没有发现反例，我就默认这个规律是成立的，然后就有了判断素数的方法isPrimeNumber。
另外值得注意的是，如果你判断n是不是素数，只要判断到√n即可，因为再让其中的一个因子递增，那么另一个因子一定会递减，又与之前的数值重复了，故无需再次判断。
具体算法见函数即可。
源代码
//C/C++实现
#include <stdio.h>
#include <iostream>
using namespace std;
int PNarray[10000] = {2}; //PNarray[0] = 2;
bool isPrimeNumber(int n, int PNarray[]){
for(int i = 0; PNarray[i] * PNarray[i] <= n; i++){
if(n % PNarray[i] == 0){
return false;
}
}
return true;
}
int main(){
int a, b;
scanf("%d %d", &a, &b);
int index = 1;
for(int i = 3; index < b; i += 2){ //建立到第b个数的素数表
if(isPrimeNumber(i, PNarray)){ //is prime number
PNarray[index++] = i; //store in prime number table
}
}
int count = 0;
for(int j = a - 1; j < b; j++){
if(count % 10 != 0){
printf("%c", ' ');
}
printf("%d", PNarray[j]);
count++;
if(count % 10 == 0){
printf("%c", '\n');
}
}
if(count % 10 != 0){
printf("%c", '\n');
}
return 0;
}
