质数
- 对所有的大于1的自然数字，定义了【质数/合数】这一概念。对于所有小于等于1的自然数，没有这个概念，它们既不是质数也不是合数。
- 质数的定义：对于大于1的自然数，如果这个数的约数只包含1和它本身，则这个数被称为质数，或者素数
质数的判定
试除法O(sqrt(n))对于一个数n，从2枚举到n-1，若有数能够整除n，则说明除了1和n本身，n还有其他约数，则n不是质数；否则，n是质数
优化：由于一个数的约数都是成对出现的。比如12的一组约数是3，4，另一组约数是2，6。则我们只需要枚举较小的那一个约数即可
我们用\(d|n\)来表示d整除n，比如\(3∣12\)，只要满足\(d|n\)，则一定有\(\frac{n}{d}|n\)，因为约数总是成对出现的，我们只需要枚举小的那部分数即可，令\(d ≤ \frac{n}{d}\)，即，\(d ≤ \sqrt{n}\)，因此对于n，只枚举2到\(\sqrt{n}\)即可。
代码模板
bool is_prime(int n) {
if(n < 2) return false;
for(int i = 2; i <= n / i; i++) {
if(n % i == 0) return false;
}
return true;
}
注意有一个细节，for循环的结束条件，推荐写成i <= n / i。有的人可能会写成i <= sqrt(n)，这样每次循环都会执行一次sqrt函数，而这个函数是有一定时间复杂度的。而有的人可能会写成i * i <= n，这样当i很大的时候（比如i比较接近int的最大值时），i * i可能会溢出，从而导致结果错误。
分解质因数
朴素思路
还是采用试除法：
对于一个整数 n 总能写成如下形式：
\(N = P_{1} ^ {k_{1}} \times P_{2} ^ {k_{2}} \times \dots \times P_{n} ^ {k_{n}}\)，其中\(P_{1} \dots P_{n}\) 都是质数，\(k_{1} \dots k_{n}\) 都是大于等于0的正整数。
对于一个数求解质因数的过程：从2到n，枚举所有数，依次判断是否能够整除 n 即可。
求质因数分解，为什么枚举所有数，而不是枚举所有质数，万一枚举到合数怎么办？解释：枚举数时，对于每个能整除 n 的数 i，先把这个数除干净了，再继续枚举后面的数，这样能保证，后续再遇到能整除的数，一定是质数而不是合数。
例如：求180的质因数分解
- i = 2 n = 180 / 2 = 90 / 2 = 45
- i = 3 n = 45 / 3 = 15 / 3 = 5
- i = 4 当i是合数时，i 一定不能整除 n 。如果 4 能整除 n 那么 2 一定还能整除 n，就是在 i = 2的时候没有除干净，而我们对于每个除数都是除干净的，因此产生矛盾。
- i = 5 n = 5 / 5 = 1
void divide(int n) {
for(int i = 2; i <= n; i++) {
if(n % i == 0) {
int s = 0;
while(n % i == 0) {
s++;
n /= i;
}
printf("%d %d\n", i, s);
}
}
}
优化 O(sqrt(n))
性质：n中只包含一个大于\(\sqrt{n}\)的质因子，很好证明，如果中包含两个大于\(\sqrt{n}\)的质因子，那么乘起来就大于n了
因此，在枚举的时候可以先把2到\(\sqrt{n}\)的质因子枚举出来，如果最后处理完n > 1,那么这个数就是那个大于\(\sqrt{n}\)的质因子，单独处理一下就可以
void divide(int n) {
for(int i = 2; i <= n / i; i++) {
if(n % i == 0) {
int s = 0;
while(n % i == 0) {
s++;
n /= i;
}
printf("%d %d\n", i, s);
}
}
if (n > 1) printf("%d %d", n, 1);
}
筛质数
朴素筛法
将2到n全部数放在一个集合中，遍历2到n，删除集合中这个数的倍数。最后集合中剩下的数就是质数。
解释：如果一个数p没有被删掉，那么说明在2到p-1之间的所有数，p都不是其倍数，即2到p-1之间，不存在p的约数。故p一定是质数。
时间复杂度：\(\frac{n}{2} + \frac{n}{3} + \dots +\frac{n}{n} = n\ln_{}{n} < n\log_{2}{n}\)故，朴素思路筛选质数的时间复杂度大约为O(nlogn)
埃氏筛法
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) ptimes[ctn++] = i; // i是质数
for(int j = i; j <= n; j += i) st[j] = true; // 删数
}
}
其实不需要把全部数的倍数删掉，而只需要删除质数的倍数即可。
对于一个数p，判断其是否是质数，其实不需要把2到p-1全部数的倍数删一遍，只要删掉2到p-1之间的质数的倍数即可。因为，若p不是个质数，则其在2到p-1之间，一定有质因数，只需要删除其质因数的倍数，则p就能够被删掉。埃氏筛法筛选质数的时间复杂度大约为O(nloglogn)
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) {
ptimes[cnt++] = i; // i是质数
for(int j = i; j <= n; j += i) st[j] = true; // 删数
}
}
}
线性筛法(欧拉筛)
大体思路和埃氏筛法一样，将合数用他的某个因数筛掉，其性能要优于埃氏筛法（在\(10^{6}\)下两个算法差不多，在\(10^{7}\)下线性筛法大概快一倍）核心思路是：对于某一个合数n，其只会被自己的最小质因子给筛掉
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) ptimes[cnt++] = i; // i是质数
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
对上面的代码解释如下：
用pj来表示primes[j]
- 当
i % pj == 0时:pj 一定是 i 的最小质因子，因为我们是从小到大枚举质数的，首先遇到的满足i % p j == 0的，pj 一定是 i 的最小质因子，并且pj 一定是\(pj \times\) i的最小质因子。比如，\(15 = 3 \times 5\)，15的最小质因子是3，则15的倍数中最小的数，且最小质因子同样是3的，一定是给15乘以一个最小质因子3，即45。 - 当
i % pj != 0时:pj 一定不是 i 的质因子,并且由于是从小到大枚举质数的，那么 pj 一定小于 i 的全部质因子。那么 pj 就一定是 \(pj \times i\) 的最小质因子。
因此，则无论哪种情况，pj都一定是 \(pj \times i\) 的最小质因子。
如何保证所有合数都被筛掉， 对于一个合数x，当枚举到 x / pj 时，就会被删掉，因此每个合数都会被筛掉
线性筛法保证了，每个合数，都是被其最小质因子给删掉的，且只会被删一次
约数
求一个数的所有约数O(sqrt(n))
利用试除法求一个数的所有约数，思路和判断和质数的判定类似
约数都是成对出现的，只需要枚举1到\(\sqrt{n}\)即可
vector<int> get_dividers(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;
}
约数个数/约数之和
将一个数N分解质因数为\(N=P_{1} ^{k_1} \times P_{2} ^{k_2} \times P_{3} ^{k_3} \dots \times P_{n} ^{k_n}\)
定理1：约数的个数为\((k_{1} + 1) \times (k_{2} + 1) \times \dots \times (k_{n} + 1)\)
定理2：所有约数之和为\((P_{1}^{0} + P_{1} ^ {1} + \dots + P_{1} ^{k_1}) \times (P_{2}^{0} + P_{2} ^ {1} + \dots + P_{2} ^{k_2}) \times \dots \times (P_{n}^{0} + P_{n} ^ {1} + \dots + P_{n} ^{k_n})\)
最大公约数(欧几里得算法/辗转相除法)
性质：gcd(a,b) == gcd(b, a % b)
证明：假设\(`a`\)和\(`b`\) 的最大公约数为\(`k`\) ，则可以写成\(`a = a_{k} \times k\)，\(b = b_{k} \times k\)，那么$a_{k}$ 和 $b_{k}$一定是互质的，由于公式需要a mod b ，则把$a$写成 $a = c \times b + d$，即 a mod b = d，带入$b = b_{k} \times k$，则$a = c \times b_{k} \times k + d = a_{k} \times k$，消去$k$得到$c \times b_{k} + \frac{d}{k} = a_{k}$ ，因为$a_{k}$是整数，则$\frac{d}{k}$也是整数 ，因此$d$是$k$的倍数，但是gcd(b,d)一定是$k`$吗？
反证法：假设gcd(b,d)$=k^{’} > k$,令\(`b = b_{k}^{’} \times k^{’}`\),\(`d = d_{k}^{’} \times k^{’}`\),带入到\(`a = c \times b + d`\) ，得到\(`a = c \times b_{k}^{’} \times k^{’} + d_{k}^{’} \times k^{’}`\)，那么\(`a`\)和\(`b`\) 的最大公约数为就会等于\(`k^{’}`\)，产生矛盾。得证，gcd(a,b) == gcd(b, a % b)
代码模板
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}