TB椰程 TypeBuddy 打字搭子

质数筛

洛谷·深入浅出 · 代码 · cpp · 难度 2/5 · 共 566 字

从给定数列中筛出并依次输出质数

  • 洛谷
  • 例题

正文

// 原题：https://oj.yecheng.tv/p/1430
// 题意：读入 n 个数，去掉非质数，按原顺序输出剩下的质数，空格隔开。
// 思路：逐个用试除法判质数（1 不是质数），是质数就输出。
// 复杂度：O(n * sqrt(max))。
// 易错点：1 不是质数；输出顺序保持原序，不要排序。
#include <iostream>
#include <vector>
using namespace std;
bool isprime(int x){
    if(x < 2) return false;
    for(int i = 2; i * i <= x; i++) if(x % i == 0) return false;
    return true;
}
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++)
        if(isprime(a[i])) cout << a[i] << " ";
    cout << endl;
    return 0;
}

洛谷·深入浅出的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK