「数学::质数」试除法 / 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;
}