P5736 【深基7.例2】质数筛——题解

解题思路

对每个数单独判断是否为质数。若 $x$ 有非平凡因数，那么其中至少有一个不超过 $\sqrt{x}$，所以只需试除到平方根。判断为质数后按原顺序输出。

复杂度分析

时间复杂度 $O(n\sqrt A)$，其中 $A=\max a_i$；额外空间 $O(1)$。

易错点

数字 $1$ 不是质数。循环条件用 1LL*i*i<=x 避免乘法溢出。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
bool prime(int x){
    if(x<2) return false;
    for(int i=2;1LL*i*i<=x;i++) if(x%i==0) return false;
    return true;
}
int main(){
    int n;cin>>n;bool first=true;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        if(prime(x)){
            if(!first) cout<<' ';
            cout<<x;first=false;
        }
    }
    cout<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; bool prime(int x){ if(x<2) return false; for(int i=2;1LLii<=x;i++) if(x%i==0) return false; return true; } int main(){ int n;cin>>n;bool first=true; for(int i=0;i<n;i++){ int x;cin>>x; if(prime(x)){ if(!first) cout<<' '; cout<<x;first=false; } } cout<<'\n';return 0; }