【深基7.例2】质数筛

题目链接 : https://www.luogu.com.cn/problem/P5736

题目描述

输入 $n$ 个不大于 $10^5$ 的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。

输入格式

第一行输入一个正整数 $n$，表示整数个数。

第二行输入 $n$ 个正整数 $a_i$，以空格隔开。

输出格式

输出一行，依次输出 $a_i$ 中剩余的质数，以空格隔开。

样例 #1

样例输入 #1

5
3 4 5 6 7

样例输出 #1

3 5 7

提示

数据保证，$1\le n\le100$，$1 \leq a_i \leq 10^5$。

AC code

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
bool is_prieam(int n){
     if(n<=1) return false; // < 0 肯定不是质数
      for(int i = 2;i<=sqrt(n);i++){ // 对 1 - n 开平方根的范围内遍历
            if(n%i==0) return false; // 整除 返回 false
      }
      return true;
}
int main()
{
     vector<int>nums;
     int n;
     cin>>n;
     nums.resize(n);

     for(int i = 0;i<n;i++)cin>>nums[i];

     for(int x:nums) if(is_prieam(x))cout<<x<<' ';
}