PAT 1013 数素数

PAT

字数统计: 375阅读时长: 1 min

 2019/03/21   Share

PAT 1013 数素数（20分）

令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤104，请输出 PM 到 PN 的所有素数。

输入格式：

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

输出格式：

输出从 PM 到 PN 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

1
2
3

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 个素数，然后，再输出。

输入问题，判断从第 M 个素数开始，才写入 vector 容器中，第 M 个之前的都不写入。再设置一个参数 cnt ，每次写入之后加 1，到第 N 个停止。

#include<iostream>
#include<vector>
using namespace std;
bool isprime(int a) {
    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;
    vector<int> v;
    cin >> M >> N;
    while(cnt < N){            //当素数个数小于最大的 N 时,继续写入 v 中
        if( isprime(num)){
            cnt++;                //素数判断基数增加 1
            if(cnt >= M) v.push_back(num);     //如果这个素数是第 M+ 个素数(包括第 M 个),写入 v
        }
        num++;              //总素数个数增加 1

    }
    cnt = 0;
    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;
}

Next Post

PAT 1014福尔摩斯的约会
Previous Post

C语言字符串浅析 Character String (C)

CATALOG

1. PAT 1013 数素数（20分）

