「数学::质数」试除法 / Luogu P5736（C++）

概述

在质数的第一节我们来讲解试除法。

质数是指在大于1的自然数中只能被1和它自己整除的数。

我们可以利用这一除法性质对质数进行判定。

Luogu P5736：

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

思路

如果一个数不是质数，即合数，那么它一定可以被除1和它自己以外的数整除。

如果有合数a，那么必有a%b==0。其中b!=a&&b!=1。

因此对于一个数x，因此我们可以从2开始枚举自然数到x-1，判断其中是否有可以整除x的数，如果有，则x不是质数。

但是对于单个数n进行判断，这样做的时间复杂度就已经是O(n)级别的了，该怎么优化呢？

注意到：如果a是合数，b是a的一个因数，则c=a/b也是a的一个因数。

因此对于一对数（b,a/b），只需要检验其中较小的那个是否是a的因数即可，即min(b,a/b)。

当b=c时，√a=b=c，即较小的因数最大为√a，所以我们只需要枚举[2,√a]就能断定a是否为质数。

综上：

如果x是一个合数，那么枚举[2,√x]就能检验出其为合数。

如果x是一个质数，那么枚举[2,√x]时就没有任何一个数整除它，那么[√x,x)必然不能整除它，不必检验。（因数是成对出现的，小的分布在[2,√x]，大的分布在[√x,x)，小的不存在则大的一定不存在）

算法过程

我们来实现质数判断函数。

 很直观的代码：

bool is_prime(int& num){
    if(num<2)return false;
    for(int i=2;i*i<=num;i++)
        if(!(num%i))return false;
    return true;
}

小于2的数不是质数。

对于大于2的数，枚举从2开始的自然数，他们在[2,√x]之间，num一旦被整除就返回false，否则返回true。

复杂度

时间复杂度: O(√n)
空间复杂度: O(1)

Code

#include <iostream>
using namespace std;
bool is_prime(int& num){
    if(num<2)return false;
    for(int i=2;i*i<=num;i++)
        if(!(num%i))return false;
    return true;
}
int main(){
    int n;cin>>n;
    int num,cnt=0,ans[n]={0,};
    while(n--){
        cin>>num;
        if(is_prime(num))ans[cnt++]=num;
    }
    for(int i=0;i<cnt;i++)cout<<ans[i]<<' ';
    return 0;
}