质数定义:一个数只能被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]);
}
}