质数 & 约数
质数
- 定义：在大于1的整数中，如果只包含1和本身这两个约数，就称为质数，或素数
- 判定：试除法
- 分解质因数
- 筛法求质数
- 朴素筛法，埃氏筛法
- 线性筛法
试除法判定质数 —— 模板题 AcWing 866. 试除法判定质数
- 暴力枚举
2~n-1的所有数,判断n是否存在除自身外的其他约数 - 可以发现，若 $d|n$,则 $\frac{n}{d}|n$。因此可以枚举到 $\sqrt{n}$
时间复杂度：$O(\sqrt{n})$
模板
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
/*
这里不推荐写sqrt(n)和i * i
sqrt函数执行速度较慢
i * i存在溢出的情况
*/
if (x % i == 0)
return false;
return true;
}
试除法分解质因数 —— 模板题 AcWing 867. 分解质因数
- 暴力：从小到大尝试 $n$ 的所有因数
- 优化
- n中最多只包含一个大于 $\sqrt{n}$ 的质因子
- 因此可以枚举 $2$ ~ $\sqrt{n}$ 的所有数，之后处理一下大于 $\sqrt{n}$ 的质因子即可
时间复杂度：最坏 $O(\sqrt{n})$（所有 $2 - \sqrt{n}$ 的数全遍历），最好 $O(logn)$ (x为某一个数的n次方)
模板
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
//x的质因子中不包含2~i-1中的任意一个数，因此这句话成立意味着i为质数
{
int s = 0;
while (x % i == 0) x /= i, s ++ ; //确保x的质因子中不包含2~i-1中的任意一个数
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
朴素筛法求素数 —— 模板题 AcWing 868. 筛质数
- 从前往后遍历，每当找到一个质数，就把后面所有是该质数倍数的数删掉
- 优化：只需要把质数的倍数筛掉即可
时间复杂度：原始版$O(nlogn)$，优化版 $O(n \log\log n)$
- 分析：对于一个数 $i$,删除操作的循环次数是 $\frac{n}{i}$
- 总时间：$$\sum_{i=2}^{n}\frac{n}{i}=n\sum_{i=2}^{n}\frac{1}{i}$$ $$\sum_{i=1}^{n}\frac{1}{i}=\ln n+c$$
- 因此总时间复杂度就是$O(n\log n)$
- 优化：只需要把质数的倍数筛掉即可
- 1~n中有 $\frac{n}{\ln n}$ 个质数，数据规模降低了 $\ln n$ ,因此时间复杂度也降低 $\ln n$ ,接近 $O(n)$ (实际是 $O(n \log\log n)$)
模板
原始版
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
}
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
优化版(埃氏筛法，埃拉托斯特尼筛法),重点掌握思想
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
线性筛法求素数 —— 模板题 AcWing 868. 筛质数
- 每个合数都被最小质因子筛掉
- 线性筛法也称欧拉筛法
时间复杂度：$O(n)$
模板
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ ) //中间条件一定要，否则st[primes[j] * i]会越界
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
证明上述代码的合理性
- 由于primes中存储的质数是从小到大排列的，所以
- 当
i % primes[j] == 0时，primes[j]一定是primes[j] * i的最小质因子 - 当
i % primes[j] != 0时，primes[j]一定小于 $i$ 的最小质因子，所以primes[j]也一定是primes[j] * i的最小质因子
- 当
- 对于每个合数 $x$ ,设 $x$ 的最小质因数为 $p_j$.当遍历到 $x/p_j$ 时，x一定会被筛掉
-
由于每个合数只有一个最小质因子，因此每个数只会被筛一次，所以是线性的
约数
- 试除法求所有约数
- 约数个数
- 约数之和
- 最大公约数
- 欧几里得算法（辗转相除法）
试除法求所有约数 —— 模板题 AcWing 869. 试除法求约数
- 在试除法找质数的基础上用数组存下每个数的质因数
时间复杂度：$O(\sqrt{n})$
- 数论题要记得算时间复杂度
- 求 1~n 中所有数的约数总数，相当于求所有数在 1~n 中的倍数的总数，就是 $$\sum_{i=2}^{n}\frac{n}{i}=n\sum_{i=2}^{n}\frac{1}{i}$$
- 平均下来每个数的约数个数期望值就是 $\log n$ ,因此排序的时间复杂度就是 $O(\log n \log\log n)$ ,远小于 $O(\sqrt{n})$ ，可以忽略不记
模板
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
约数个数和约数之和 —— 模板题 AcWing 870. 约数个数, AcWing 871. 约数之和
- 算数基本定理
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
存每个质数对应的次数可以用unordered_map
欧几里得算法 —— 模板题 AcWing 872. 最大公约数
- 原理：
gcd(a,b) = gcd(b,a % b) - 证明：
- 设 $m$ 为 $a,b$ 的最大公约数。若$a \div b=c…d$，则
a % m = (b*c+d) % m = b*c % m + d % m = d % m - 因为
a % m == 0,所以d % m == 0,所以gcd(a,b) = gcd(b,a % b)
- 设 $m$ 为 $a,b$ 的最大公约数。若$a \div b=c…d$，则
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
作者：yxc
链接：https://www.acwing.com/blog/content/406/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
