【深基7.例2】质数筛

解题思路

先读入数组，再依原顺序检查每个数。对 x 从 2 试除到平方根，无因子时就是质数。

正确性说明

合数一定有一个不超过平方根的非平凡因子；排除 1 后，未找到因子的数就是质数。按数组顺序输出保持原顺序。

易错点

1 不是质数；不排序，不去掉重复出现的质数。

复杂度

n 个数的最大值为 A，时间 O(n√A)，空间 O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    bool first = true;
    for (int x : a) {
        bool prime = x >= 2;
        for (int d = 2; d * d <= x; d++)
            if (x % d == 0) {
                prime = false;
                break;
            }
        if (prime) {
            if (!first)
                cout << " ";
            cout << x;
            first = false;
        }
    }
    cout << "\n";
    return 0;
}