1013 数素数 (20分)c++实现

令 P_​i​​ 表示第 i 个素数。现任给两个正整数 M≤N≤10^​4​​，请输出 P_​M​​ 到 P​_N​​ 的所有素数。

输入格式：

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

输出格式：

输出从 P_​M​​ 到 P​_N​​ 的所有素数，每 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

思路： 1、创建一个大小为max动态数组来接受素数，因为第10000个素数是104729，在遍历寻找判断素数需要大于104729。 2、是用容器来写，思路同上，容器的方法我觉得更加精简。

动态数组代码：

#include<iostream> #include<cmath> using namespace std; bool isprime(int a) { bool flag = true; for (int j = 2; j <=sqrt(a); j++) { if (a % j == 0) //判断a不是素数 { flag = false; break; } } return flag; } int main() { int min, max, count = 1, count1 = 1,count2=1; cin >> min >> max; int* pd = new int[max]; pd[0] = 1; for (int i = 2; i <=105000; i++) { if (isprime(i)) { if (count<=max) { pd[count] = i; count++; } } } for (int i =min; i <=max; i++) { cout << pd[i]; if (count1 % 10 != 0 && count2<(max-min+1)) { cout << " "; } else cout << endl; count1++; count2++; } delete []pd; return 0; }

容器代码：

#include<iostream> #include<cmath> #include<vector> using namespace std; bool isPrime(int a)//判断是否为素数 { bool flag = 1; for (int i = 2; i <= sqrt(a); i++){ if (a % i == 0){ flag = 0; return flag; } } return flag; } int main() { int min, max; cin >> min >> max; vector<int>v; for (int i = 1; i < 105000; i++){//第10000个素数是104729 if(isPrime(i)) v.push_back(i);//如果是素数，就插入到容器中 if (v.size() == max+1)//如果达到了题目要求的最大素数数目+1（因为1不是素数，所以会占一个位置为v[0]）停止循环 break; } for (int i = min; i < v.size(); i++){ cout << v[i]; if ((i - min+1) % 10 != 0 && i != max)//每整除10换行，不到10输出空格,i!=max保证输出最后一个数后面没有空格 cout << " "; else cout << endl; } return 0; }