1.题目介绍
【深基7.例2】质数筛
题目描述
输入 \(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\)。
2.题解
2.1 子程序
思路
只要知道 如果一个数是质数,有 num = m * n;(m,n != 1,num), 如果有一个因子 m >= sqrt(num), 那么必然有另一个因子 n <= sqrt(num),所以我们只要找到这个n是否存在即可
代码
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int num){
if(num == 1) return false;
else if(num == 2) return true;
for (int i = 2; i <= sqrt(num); i++){
if (num % i == 0) return false;
}
return true;
}
int main(){
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++){
cin >> arr[i];
if(is_prime(arr[i])) cout << arr[i] << ' ';
}
}
标签:P5736,int,质数,深基,样例,arr,num
From: https://www.cnblogs.com/trmbh12/p/17990825