P76045 保留质数 — 题解

专题： 函数
适用题目： 新生 OJ 本地题包中的 P76045，不要直接用于外站同名题。

解题思路

先写 is_prime(x) 判断 x 是否为质数，再对每个输入值调用并筛出质数。

复杂度

时间 $O(n\sqrt M)$，空间 $O(n)$。

易错点

1 不是质数；循环判断时避免重复输出空格。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int is_prime(int x){
    if(x<2)return 0;
    for(int d=2;1LL*d*d<=x;d++)if(x%d==0)return 0;
    return 1;
}
int main(void) {
    int n;scanf("%d",&n);int *a=malloc(n*sizeof(int)),cnt=0;
    for(int i=0;i<n;i++){scanf("%d",&a[i]);if(is_prime(a[i]))cnt++;}
    printf("%d\n",cnt);int first=1;
    for(int i=0;i<n;i++)if(is_prime(a[i])){
        if(!first)putchar(' ');printf("%d",a[i]);first=0;
    }
    putchar('\n');free(a);return 0;
}

C++17 参考程序

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

bool is_prime(int x) {
    if (x < 2) return false;
    for (int d = 2; 1LL * d * d <= x; d++) if (x % d == 0) return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (is_prime(x)) a.push_back(x);
    }
    cout << a.size() << '\n';
    for (int i = 0; i < (int)a.size(); i++) cout << a[i] << (i + 1 == (int)a.size() ? '\n' : ' ');
    if (a.empty()) cout << '\n';
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。