质数筛（好题 1）

题目

质数筛

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

输入格式

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

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

输出格式

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

代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[100];
    int m;
    int o = 0;   // 记录质数的个数

    for (int i = 0; i < n; i++) {
        cin >> m;   // 依次读入这 n 个数字

        int s = 0;
        // 【优化】判断质数只需要从 2 遍历到 sqrt(m) 即可，效率提升极大
        for (int t = 2; t * t <= m; t++) {
            if (m % t == 0) {
                s++;
            }
        }

        // 【修复】加上 m > 1，排除数字 1 的干扰
        if (s == 0 && m > 1) {
            a[o] = m;
            o++;
        }
    }

    for (int i = 0; i < o; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

两个关键点

只试到 √m：若 m 有因数 t，那么 m/t 也是因数，且两者必有一个 ≤ √m。所以 t * t <= m 就够，不用 t < m。写成 t * t 而不是 t <= sqrt(m)，还能避免浮点误差和额外的 <cmath> 依赖。
1 不是质数：m > 1 这个条件不能省，否则输入 1 会被当成质数输出。

另外 a[100] 是按「最多 100 个数」开的，如果 n 可能更大，数组要跟着放大（或用 std::vector）。