数论补完计划 Part1 基本定理、质数与约数

基本定理

算术基本定理

任何一个合数均可被唯一分解成若干质数的乘积。

也就是说任何合数都可以唯一地表示成 的形式，这条定理在之后的质数筛中有大用。

素数定理

中的质数个数约等于

可以用来粗略估计在当前数据范围下质数的个数，以便更具有针对性的选用质数筛法。据说这个定理有一个非常初等的证明，仅涉及到极限、自然对数函数和指数函数的一些简单性质（子供向），非常适合初中生茶余饭后作为谈资。

费马小定理

对于一个质数 ，以及一个正整数 。如果 不是 的倍数，那么

它是质数模数逆元求解的理论基础，在大部分情况下，它还可以拿来检验一个数是否是质数（有特例，例如 ）。

欧拉定理

若 ，那么

其中 为欧拉函数，代表 内与 互质的数的个数。当 为质数时满足 ，不难发现费马小定理是欧拉定理在 为质数时的特殊情况。

威尔逊定理

对于任意质数 ，满足

上式还等价于 。可以用作质数检验，但是要算阶乘，开销方面还不如试除法。

质数

我们定义，如果一个大于一的自然数 不包含 和 外的其他约数，那么 是一个质数，反之即为合数。特别地， 既不是质数，也不是合数。

在保证正确的情况下，最快的质数判断法是 的试除法。如果我想要一次性找出 内的所有质数该怎么办呢？此时就需要质数筛了。

埃氏筛

由古希腊数学家埃拉托斯特尼发明的质数筛法。它首先找到一个质数 ，然后在 内枚举它的倍数并标记为合数，然后循环往复得到所有范围内的质数。

这个算法的核心就是算术基本定理，任何质数都可以被分解为若干质数的乘积，因此只要对质数的倍数进行筛选，就一定能保证正确性。

线性筛

它断言每个合数只会被它最小的质因子筛掉，因此我们只需要筛去以当前质数为最小质因子的合数即可。

1
2
3
4
5
6
7
8
9

void get(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) prime[cnt++] = j;
        for (int j = 1; prime[j] <= n / i; j++) {
            vis[prime[j] * i] = true;
            if (i % prime[j] == 0) break; // 不再是最小质因子了，跳出
        }
    }
}

常数筛/直取筛

顾名思义，就是 的打表。虽然这听起来非常的荒谬，但是有些时候还是可以用上的。它结合了上述的任何一种筛法，以及一个字符串格式化输出系统。代码实现很基础，不放了😎。

约数

也叫因数，当 能被 整除时，即 时，就称 是 的一个因数。

求约数仍然是试除法，需要注意的是当前数是否是一个完全平方数，以防止重复记录约数 。

最大公约数

欧几里得算法/辗转相除法用来求解两个数的最大公约数。它的核心是 的递归式，终点是 ，此时 为所求。C++ 内置的 __gcd() 函数可以做到这一点（两个下划线）。

最小公倍数

小学时讲过这样一个性质，最大公约数和最小公倍数的乘积等于两数之积。因此直接根据公式导出即可。