质数定义：一个数只能被1和自己整除，即因数只有1和本身
1.试除法 $O(\sqrt{N})$
通过定义，我们清楚地明白，对于一个数n，我们只要判断它的因数有几个，就可以判断它是不是质数了。那么我们只要判断n能否整除2到n-1这个区间中的一个整数即可判断。
但是在数据过大时会有超时的现象，这时我们可以进行优化。
一个数n若能被a整除(a不为1或n)，则一定存在一个a使得a小于$\sqrt{n}$。
n/a=b（a，b均为整数）
证：如果a$\leq$$\sqrt{n}$，显然成立，如果a大于$\sqrt{n}$，则b一定小于$\sqrt{n}$，假设成立。
综上所述，一个不是质数的数一定存在一个小于等于$\sqrt{n}$的因数。
所以在判断一个数是否是指数是，只需判断[2,\sqrt{n}]是否存在一个数为n的因数，即是否存在一个数能整除n即可。
代码：
#include <stdio.h>
using namespace std;
int n,a,b;
int main(){
scanf("%d",&n);
while(n--){
b=1;
scanf("%d",&a);
for(int i=2;i<=a/i;i++){//i<=a/i可以防止i*i过大，如果循环判断条件为i*i<=a，会出现i*i爆的现象
if(a%i==0) {
b=0;
break;
}
}
if(b==1&&a!=1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}2.Eratoshenes(埃氏筛)：
用试除法在只判断一个数时，$O(N)$的复杂度自然是较优的，但是当判断的数较多时，显然是会超时的，这里介绍一下埃氏筛。
埃氏筛是一种复杂度接近线性筛的算法。 时间复杂度$O(NloglogN)$
原理：
通过对质数概念的讲解，我们清晰地明白，一个数是质数，当且仅当它的因数只有1以及本身。那么换种说法，相当于一个数如果是质数，那么它一定是小于它的某个数（除1以外）的倍数。那么代码就很好写了，我们只要把所有<=N的数的倍数都标记成非质数即可。
对于这个算法，我们可以进行进一步优化。在讲解试除法时，我们明白，如果一个数a不是质数，那么它一定有一个小于$\sqrt{a}$的因数b，并且它一定是这个因数b大于或等于$\sqrt{b}$的倍数，所以对于一个非质数a，一定有一个小于$\sqrt{a}$的因数b，使得$b \times c$等于a，（c>=b）所以对于第二层循环我们就可以进行优化。只要从$b^2$开始即$b \times b$开始筛即可。
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
const int N=1e6+10;
int n,ans;
bool a[N];
void shai(){
a[0]=a[1]=1;//0,1都不是质数，这容易忘记（对，我忘记了回来补的）
for(int i=2;i<=N;i++){
for(int j=i;j<=N/i;j++){
a[i*j]=1;
}
}
}3.线性筛
埃氏筛之所以会有重复筛的情况，就是因为一个数的因数搭配不唯一，一个人数有多种因数搭配。
如：$16=2 \times 8=4 \times 4=8 \times 2$，虽然我们通过一部分优化省去了一些不必要的循环，但是还是没有达到真正的线性筛。那么重要的就是要找到唯一的可以确定一个数的因数搭配的方法，这就是用质因数来确认一个数。
如$16=2 \times 2 \times 2 \times 2$
$12=2 \times 2 \times 3$
$24=2 \times 2 \times 2 \times 3$
那么思路就很清晰了，分解质因数中每个数的质因子一定都是质数，质数的最小质因子就是它本身。
算法思路：运用一个整型数组v[N]来表示每个数的最小质因子，初始时全部为0.再运用一个数组prime[]，来表示第几个质数是多少。
代码解释：
第一层循环i从2到n，表示目前在筛的数，如果v[i]为0，则表示i没被小于i的数筛过，因此i为质数，此时v[i]=i,prime[++m]=i;第二层循环从prime[1]到prime[m]，及现在筛出来的质数。如果prime[i]>v[i]，即该质数大于i的最小质因子，此时没有进行的必要，因为之后或者之前肯定已经筛过了，这样会导致重复。此时直接break即可，如果i$\times$prime[m]超出了n的范围，那么也没必要再运行了，直接break即可。
总结：
线性筛通过判断最小质因子是否为本身来判断质数。之后在循环中更新后续数的最小质因子，以此来维护整个数列。
#include <iostream>
#include <stdio.h>
using namespace std;
const int N=1e8+10;
int v[N];
int pri[N],cnt;
int n,m;
void shai(){
for(int i=2;i<=n;i++){
if(!v[i]) {v[i]=i;pri[++cnt]=i;}
for(int j=1;j<=cnt;j++){
if(pri[j]>v[i]||pri[j]>n/i) break;
v[i*pri[j]]=pri[j];
}
}
}
int main(){
scanf("%d%d",&n,&m);
shai();
for(int i=1;i<=m;i++){
scanf("%d",&n);
printf("%d\n",pri[n]);
}
}