题意

输入 n 个不超过 100000 的正整数，按原顺序输出其中所有质数。

思路

先写一个质数判断函数：

• 小于 2 的数不是质数；
• 从 2 开始试除；
• 只需要检查到 divisor * divisor <= x，因为如果 x 有大于平方根的因子，必然还有一个小于平方根的配对因子。

然后扫描输入数组，保留所有满足 is_prime(x) 的数。

数据只有 n <= 100，试除法足够。题目名叫“质数筛”，但这里直接判断每个数更适合初学函数练习。

Python 知识

• /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：list(map(int, input().split())) 读取整数数组。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：列表推导式 [x for x in numbers if ...] 适合筛选结果。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：用 divisor * divisor <= x 避免浮点平方根误差。
• print(*answer) 按空格输出列表元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def is_prime(x):
    if x < 2:
        return False
    divisor = 2
    while divisor * divisor <= x:
        if x % divisor == 0:
            return False
        divisor += 1
    return True


n = int(input())
numbers = list(map(int, input().split()))

answer = [x for x in numbers if is_prime(x)]
print(*answer)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

// 判断一个数是否为质数
bool is_prime(int x) {
    if (x < 2) return false;
    // 只需检查到平方根，因为因子成对出现
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int n, x;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (is_prime(x)) cout << x << " ";
    }
    return 0;
}

复杂度

设最大数为 A，共有 n 个数。每个数试除到平方根，时间复杂度是 $O(n\sqrt A)$，空间复杂度是 $O(n)$。

总结

质数判断适合封装成函数。筛选数组时，列表推导式能清楚表达“保留满足条件的元素”。