算术基本定理#

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

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

素数定理#

中的质数个数约等于

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

费马小定理#

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

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

欧拉定理#

若 ，那么

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

威尔逊定理#

对于任意质数 ，满足

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

埃氏筛#

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

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

线性筛#

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

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

常数筛/直取筛#

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

最大公约数#

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

最小公倍数#

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