质数
2026-04-14
简介
质数是指大于 1 的自然数,且其仅有自己与 1 两个约数。
定理
1∼n 内质数个数约为 lnnn 个。
根据唯一分解定理,N=p1k1p2k2⋯pnkn。
约数个数:(k1+1)×(k2+1)×⋯×(kn+1)。int 范围内,约数个数最多的数(191745944200 和 232113511400)有 1536 个约数。
约数和:(p10+p11+⋯+p1k1)×(p20+p21+⋯+p2k2)×⋯×(pn0+pn1+⋯+pnkn)。
方法
试除法
判定一个数是否为质数:
显然, n 的因子是成对出现的,若一个为 d,则另一个为 dn,所以判定质数是只需要找 d≤dn 的数,即 d≤n。
时间复杂度 O(n)。
找一个数的所有约数: 与判定相同,也是 d≤n,每次对当前的 d 一直取出直到没有 d 这个约数,全部判断一遍即可。
但是,按照这种方法最坏复杂度为 O(n),考虑将其优化掉,我们发现,在 n 中最多只有一个大于 n 的质因子(有两个相乘一定大于 n),因此,我们可以只枚举到 n,最后剩下的数若不为 1 则为这个质因子。
时间复杂度 O(logn)∼O(n)。
质数筛
判定从 1∼n 的所有质数。
普通筛法:
对于每个 d,判定 d 的不大于 n 的倍数(不为 d 本身)并将其标记,容易发现,最后没被标记的数即为质数。
这个算法时间复杂度为 2n+3n+⋯+nn,形如调和级数(n→+∞lim2n+3n+⋯+nn=lnn+c,c 为常数),即小于 O(nlogn)。
埃拉托斯特尼筛法(埃氏筛):
在此基础上,每个数我们都进行了判断倍数其实是多余的,可以只对不大于 n 的质数进行判断,复杂度为 O(nloglogn)。
线性筛(欧拉筛):
线性筛主要思想是保证每个数只被其最小质因子标记。
具体的,若当前数 d 为质数表(单调递增)中某个数 p 的倍数,如果继续筛 p 的下一个数 p′,则由于 d 为 p 倍数,则在新数 d×p′ 中一定包含 p 这个因数,又因为 p<p′,即 d×p′ 的最小质因数实际为 p,所以应在 d 为 p 倍数是结束这一轮标记。
时间复杂度 O(n)。
