pat1013数素数 (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

分析：vector中保存第M到第N个素数，⽤cnt标记输出了多少个，如果当前已经输出的个数为10的倍 数，则输出⼀个空⾏～

#include <iostream>
#include <vector>
using namespace std;
bool isprime(int a) {				//判断传过来的是不是质数，如果不是返回false，是返回true
 for (int i = 2; i * i <= a; i++)
 if(a % i == 0) return false;
 return true;
}
int main() {
 int M, N, num = 2, cnt = 0;
 cin >> M >> N;
 vector<int> v;
 while (cnt < N) {	
     if (isprime(num)) {
         cnt++;
     if (cnt >= M) v.push_back(num);
     }
     num++;
 }
    
 cnt = 0;	//剩下部分用来解决输出相关问题，包括空格、一行10个
 for (int i = 0; i < v.size(); i++) {
     cnt++;
     if (cnt % 10 != 1) printf(" ");
     printf("%d", v[i]);
     if (cnt % 10 == 0) printf("\n");
 }
 return 0;
}

---

本系列(PAT算法)作者mail：1302304703@qq.com(非本人)