Kaygb's wiki

蓝桥算法提高-质数

资源限制

时间限制:1.0s 内存限制:256.0MB

问题描述

  给定一个正整数N,请你输出N以内(不包含N)的质数以及质数的个数。

输入格式

  输入一行,包含一个正整数N。

输出格式

  共两行。   第1行包含若干个素数,每两个素数之间用一个空格隔开,素数从小到大输出。   第2行包含一个整数,表示N以内质数的个数。

样例输入

10

样例输出

2 3 5 7 4

数据规模和约定

  N<=1000

分析

已知1不是质数,而第一个质数是2,首先判断输入是否为3,如果为3则直接输出 2 (endl) 1 ,否则先给动态数组push_back一个2,然后接下来的每个数分别除以arr中的每个数,如果能整除则不是质数直接break开始下一个数的判断

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
    vector<int> arr;
    int n,s=0;
    cin >> n;
    if (n == 3){
        cout << 2 << endl << 1;
    } else{
        arr.push_back(2);
        int flag = 0; // 是否整除
        for (int i = 3; i <n ; ++i) {
            for(vector<int>::iterator it = arr.begin();it!=arr.end();it++){
                if (i % *it == 0){
                    flag =1;
                    break;
                }
            }
            if (flag){
                flag =0;
                continue;
            } else{
                arr.push_back(i);
                s++;
            }
        }
        for(vector<int>::iterator it = arr.begin();it!=arr.end();it++){
            cout << *it;
            if (it!=arr.end()-1){
                cout << " ";
            }
        }
        cout << endl << s+1;
    }
    return 0;
}