素数

补博客ing……

素数

什么是素数?

我来引用OIwiki\mathtt{OI-wiki}上的一段话:

我们说,如果存在一个整数 kk ,使得 a=kda = kd ,则称 dd 整除 aa ,记做 dad | a ,称 aadd 的倍数,如果 d>0d > 0 ,称 ddaa 的约数。特别地,任何整数都整除 00

显然大于 11 的正整数 aa 可以被 11aa 整除,如果除此之外 aa 没有其他的约数,则称 aa 是素数,又称质数。任何一个大于 11 的整数如果不是素数,也就是有其他约数,就称为是合数。 11 既不是合数也不是素数。

素数计数函数:小于或等于 xx 的素数的个数,用 π(x)\pi(x) 表示。随着 xx 的增大,有这样的近似结果: π(x)xln(x)\pi(x) \sim \frac{x}{\ln(x)}

判断素数

怎么判断一个数是不是素数呢?

我们可以暴力解决这类问题:

从小到大枚举每个数,检验是否能够被整除,非常好理解。

code

1
2
3
4
5
6
bool isPrime(a){
if(a<2) return 0;
for(int i=2;i<a;++i)
if(a%i==0) return 0;
return 1;
}

但是……没有必要每个数都枚举一边啊!

优化

我们可以想办法来优化一下。

我们可以发现,如果xxaa的约数,那么很容易得知,ax\frac{a}{x}也一定是aa的约数。

所以,对于xxax\frac{a}{x}来说,我们只需要判断其中一个即可。

我们只判断每一对里面小的那个数。不难看出,所有较小数就是 [1,a][1, \sqrt{a}] 这个区间里的数。

由于 11 肯定是约数,所以不对它进行判断。

code

1
2
3
4
5
6
bool isPrime(a) {
if (a < 2) return 0;
for (int i = 2; i * i <= a; ++i)
if (a % i) return 0;
return 1;
}

素数筛法

素数筛应该是线性筛法中最简单的一类了。

Eratosthenes 筛法

首先来讲埃氏筛法(埃拉托尼斯筛)……

这个筛法的基本思想是:素数的倍数一定不是素数

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//洛谷题解粘的,懒得打
#include<cstring>
#include<cmath>

const int MAXN=1000010;

bool prime[MAXN];

void make_prime()
{
memset(prime,true,sizeof(prime));
prime[0]=prime[1]=false;
int t=sqrt(MAXN);
for(register int i=2;i<=t;i++)
if(prime[i])
for(register int j=2*i;j<MAXN,j+=i)
prime[j]=false;
return;
}

时间复杂度就是O(nloglogn)O(n\log\log n)

这算法还有没有优化空间呢?

我这么问就是肯定有啦!

那就要引出……当当当当

Euler 筛法

欧拉筛法

因为埃氏筛法中,每一个有多组约数的数都有可能被筛多次,例如,3030会被2,3,52,3,5各筛一次。

所以我们对其进行改进,获得欧拉筛法!

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>

const int maxn=1e7+10;

int n,m,PR[maxn],cnt;
bool pr[maxn];

int main(){
scanf("%d%d",&n,&m);
pr[0]=pr[1]=true;
for(register int i=2;i<=n;i++){
if(!pr[i]) PR[++cnt]=i;
for(int j=1;j<=cnt&&i*PR[j]<=n;j++){
pr[i*PR[j]]=true;
if(!i%PR[j]) break;
}
}
for(register int i=1;i<=m;i++){
register int x;
scanf("%d",&x);
printf("%s\n",!pr[x]?"Yes":"No");
}
return 0;
}

这样复杂度就变成了O(n)O(n)了。

还有其他素数筛法就不再多谈,因为NOIP\mathtt{NOIP}(好像要改名?)完全够用。

例题:https://www.luogu.org/problem/P1865

文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/08/16/素数/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论