主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
学习笔记——质数
最后更新于 2025-07-31 14:01:03
作者
WJX3078
分类
算法·理论
复制 Markdown
查看原文
删除文章
更新内容
从本节开始,我们将进入数学的海洋(~~希望不会溺水~~),那就从质数开始我们的数学知识之旅吧! # 1、定义 > 若一个**正整数无法被除了$1$和它自身以外的任何自然数整除**,则称该数为质数(或素数),否则称该数为合数。 > --《算法竞赛进阶指南》 在整个自然数集合中,质数的分布比较稀松,大约**每$lnN$个数中有一个质数**,即对于正整数$N$,不超过其的质数大约有$\frac{N}{lnN}$个。 # 2.质数的判定 试除法:若一个正整数$N$为合数,则存在一个能整除$N$的正整数数$T$,满足$2 \le T \le \sqrt{N}$。 理解:若存在一个正整数$M$使得$M|N$($N$被$M$整除)且$M \in (\sqrt{N},N)$,则正整数$\frac{N}{M}$也可以整除$N$且$\frac{N}{M} \in [2,\sqrt{N}]$ 所以判断一个数是否为质数,我们只需要扫描$2 - \sqrt{N} $之间的所有整数,依次判断其是否整除$N$,都不整除则$N$为质数,否则为合数。其时间复杂度为$O(\sqrt{N})$。 代码如下: ```cpp il bool id_prime(int n) { //质数返回1,合数返回0 if(n<2) return 0; //特判0和1,它们是合数 for(re int i=2;i*i<=n;++i) //依次扫描 if(n%i==0) return 0;//能被整除,就是合数 return 1;//是质数 } ``` 当然,我们也可以对其进行一些常数优化: ```cpp il bool is_prime(int n) { if(n<2) return 0; if(n==2||n==3) return 1; if(n%6!=1&&n%6!=5) return 0; for(re int i=5;i*i<=n;i+=6) if(n%i==0||n%(i+2)==0) return 0; return 1; } ``` 此方法基于一个原理: > 除$2$、$3$外的所有质数,除以$6$的余数一定为$1$或$5$。 理解:一个数除以$6$,其余数为$0$、$1$、$2$、$3$、$4$、$5$ 对于余数为$0$、$2$、$4$的数,其一定是$2$的倍数。 对于余数为$0$、$3$的数,其一定是$3$的倍数。 所以我们只要判断$N$是否整除$6n-1$或$6n+1$即可(其中$n \ge 1$且$6n+1 \le \sqrt{N}$) 这种方法常数极小,大约为$\frac{\sqrt{N}}{3}$。 # 3.质数筛 题意简述:给定一个正整数$N$,求$1-N$之间所有质数。 首先,我们想到的最朴素的想法就是枚举$1-N$,依次判断每个数是否是质数。显然,这样做太慢了,我们就可以引进一些算法来优化它。 ## Eratosthenes 筛法 就是$OIer$们口中常说的埃氏筛,它的基本思路是:任何一个整数$x$,其倍数$2x$、$3x$......$\left\lfloor\dfrac{N}{x}\right\rfloor \times x$都是合数。 实际上,**小于$x^2$的$x$的倍数在扫描更小的数时已经被标记过了**。 理解:$2x$在标记$2$时标记了,$3x$在标记$3$时标记了.....前$2$到$x-1$ $\times x$都在标记比$x$小的质数时被标记过了。 所以我们只需要从$x^2$标记到$\left\lfloor\dfrac{N}{x}\right\rfloor \times x$即可,其时间复杂度为$O(\sum_{p \le N}{\frac{N}{p}}) = O(N log log N)$,其中$p$表示小于$N$的质数。 代码如下: ```cpp bool vis[N];//标记数组 int pri[N],m;//pri[i]记录质数,m表示质数个数 il void primes(int n) { for(re int i=2;i<=n;++i) { if(vis[i]) continue;//标记过,直接下一层循环 pri[++m]=i;//统计质数 for(re int j=i;j<=n/i;++j) vis[i*j]=1;//标记i的倍数 } } ``` ## 欧拉筛(线性筛) 我们都知道,埃氏筛最大的瓶颈就是会重复标记质数(即使从$x^2$开始标记也会),那我们可不可以让每一个数只被标记一次呢?答案是肯定的,欧拉筛就给我们提供了这样的思路:其通过**从小到大累计质因子的方法**,令$vis[i]$数组只记录$i$的最小质因子,达到线性筛质数。 其过程如下: - 扫描$2$到$N$中的每个数,若`vis[i]==0`,则令`vis[i]=i`并把它保存进质数数组。 - 扫描质数数组中不大于$vis[i]$的所有质数(设为$p$),标记`vis[i*p]=p`。(因为$p \le vis[i] \le i$,所以$p$是合数$i \times p$的最小质因子) 因为每一个合数都可以被表示成$i \times p$的形式,且其只会被其最小质数$p$筛一次,所以其时间复杂度为$O(N)$。 代码如下 ```cpp int vis[N];//标记数组 int pri[N],m;//pri[i]记录质数,m表示质数个数 il void primes(int n) { for(re int i=2;i<=n;++i) { if(!vis[i]) {vis[i]=i;pri[++m]=i;}//没被标记过,是质数 for(re int j=1;j<=m;++j) {//枚举质数数组 if(pri[j]>vis[i]||pri[j]>n/i) break; //pri[j]不是i*pri[j]的最小质数或i*pri[j]>n就不用继续标记 vis[i*pri[j]]=pri[j]; //标记i*pri[j]的最小质因子pri[j] } } } ``` # 3.质因数分解 算数基本定理:任何一个大于$1$的正整数都能唯一分解为有限个质数的乘积。可写作: $$N = p_1^{c_1}p_2^{c_2}...p_m^{c_m}$$ 其中$c_i$都是正整数,$p_i$都是质数,且满足$p_1 < p_2 < ... < p_m$。 我的理解: 首先,根据质数的定义,质数只能被一和它本身整除,所以质数符合这个定理 又因为合数能被除了一和它本身的数整除(设这个数为$p$),如果$p$是质数,那就符合这个定理, 如果$p$是合数,就继续往下分。 ## 试除法 我们可以扫描$2 \sim \left\lfloor{\sqrt{N}}\right\rfloor$中的每个数$d$,若$d|N$,则从$N$中除去所有的因子$d$,同时累计除去的$d$的个数。 因为合数肯定在之前就被其质因数除去,所以最后得出的一定是质因数分解的结果,时间复杂度为$O(\sqrt{N})$。 代码如下: ```cpp int pri[N],c[N],m;//p[i]记录质因数,c[i]记录第i个质因数的个数 il void divide(int n) { for(re int i=2;i*i<=n;++i) { if(n%i==0) {//找到可以整除的数 pri[++m]=i,c[m]=0; while(n%i==0) n/=i,++c[m];//统计该质因子的个数 } } if(n>1) pri[++m]=n,c[m]=1;//如果最后n也是质数,把n加入答案数组 } ``` 例题: [P3383 【模板】线性筛素数(板子)](https://www.luogu.com.cn/problem/P3383)[(题解)](https://www.luogu.com.cn/blog/cicos/notprime)[(我的代码)](https://www.luogu.com.cn/record/48439178) [P5535 【XR-3】小道消息](https://www.luogu.com.cn/problem/P5535)[(题解)](https://www.luogu.com.cn/blog/chinaxjh/solution-p5535)[(我的代码)](https://www.luogu.com.cn/record/48439767) 本题是一道有意思的素数判断题(幸好出题人很良心),根据伯特兰-切比雪夫定理:若整数$n > 3$,则至少存在一个质数$p$,符合$n$ $<$ $p$ $<$ $2 \times n$ $-$ $2$,我们就可以对$k+1$进行分类讨论: - 若$k+1$是质数:则第一天它可以传遍所有不是它的倍数的数(质数与所有不是它倍数的数互质),第二天就可以由不是它的倍数的数$-1$传给它(相邻的两个数互质)。(显然,如果$2 \sim n+1$都没有该质数的倍数,一天就传完了) - 若$k+1$不是质数:则第一天它可以传递到一个属于$[\left\lfloor\dfrac{n}{2}\right\rfloor,n]$中的一个素数,再由该素数传递到所有数。 [AcWing196. 质数距离](https://www.acwing.com/problem/content/198/)[(题解)](https://www.acwing.com/solution/content/981/)[(我的代码)](https://www.acwing.com/problem/content/submission/code_detail/4583348/) 本题中$l$和$r$特别大,但$r-l \le 1e6$,所以我们可以预处理$2 \sim \sqrt{r_{max}}$中的所有质数,在对于每一组$l$和$r$,将$l \sim r$中间的所有质数的倍数标记,在剩下的未标记的数中找相邻的最大值和最小值即可。 注意点: - 当$l<2$是,把$l$设为$2$。 - 标记区间的合数时,可以让该区间都减去$l$,只用开一个$1e6$的$bool$数组即可。 [AcWing197. 阶乘分解](https://www.acwing.com/problem/content/199/)[(题解)](https://www.acwing.com/solution/content/4960/)[(我的代码)](https://www.acwing.com/problem/content/submission/code_detail/4583704/) 思路:因为$1 \sim n$中的数的质因子最大不超过$n$,所以可以先预处理出$1 \sim n$中的所有质数,设质数为$p$,则$N!$中质因子$p$的个数为: $$\left\lfloor\dfrac{N}{p}\right\rfloor + \left\lfloor\dfrac{N}{p^2}\right\rfloor + \left\lfloor\dfrac{N}{p^3}\right\rfloor + ... + \left\lfloor\dfrac{N}{p^{\left\lfloor{log_pN}\right\rfloor}}\right\rfloor = \sum\limits_{p^k \le N}\left\lfloor\dfrac{N}{p^k}\right\rfloor$$ 对于每个$p$,我们只需要$O(logN)$的时间计算上述和式,所以整个算法的时间复杂度为$O(NlogN)$。 # 参考资料 - 《算法竞赛进阶指南》 - [逆流之时 的博客](https://www.luogu.com.cn/blog/countercurrent-time/qian-tan-su-shuo-shai-you-hua)
正在渲染内容...
点赞
2
收藏
0