·质数
素数定理：
设 \(x \geq 1\) , 以 \(\pi(x)\) 表示不超过 \(x\) 的素数的个数。
当 \(x \rightarrow \infty\) 时，\(\pi(x) \to \dfrac{x}{\ln(x)}\)
质数筛法
1.埃式筛：从小到大一次枚举质数，将 \(\left[1, n\right]\) 内的所有倍数都标记为合数，未被标记的则为质数。
2.线性筛：保证对任一合数，只会被其最小质因数标记。对于每一个数 \(i\) ，从小到大枚举当前质数集 \(p\) ，\(p_j \leq i\) ，标记合数 \(i \times p_j\) ，若 \(p_j|i\) 说明 \(i = p_j \times u\) ；对于 \(p_j<p_k\leq i\) ，\(i \times p_k = p_j \times u \times p_k\) ，当 \(i = u \times p_k\) 时能被 \(p_j\) 筛掉的，筛质数的过程就不需要 \(p_k\) 参与了。
·约数
约数个数公式
一个整数N，可表示成 \(N = p_1 ^ {r_1} \cdot p_2 ^ {r_2} \cdot \cdots \cdot p_n^{r_n}\)
可得 \(N\) 的约数个数
·欧拉函数
欧拉函数 \(\phi(n)(n\in N^*)\) 表示小于等于你 \(n\) 的正整数中与 \(n\) 互质的个数，即：
\[\phi(n) = \sum_{i = 1} ^ n \left[\gcd(i, n) = 1\right] \]若对 \(n\) 分解质因数使得 \(n = p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}\) ，可得：
\[\frac{\phi(n)}{n} = \prod_{i = 1} ^ m (1 -\frac{1}{p_i}) \]证明1：
设 \(p_1, p_2\) 是 \(n\) 的质因数， 则在 \(\left[1, n\right]\) 有 \(\dfrac{n}{p_1}\) 个 \(p_1\) 倍数，有 \(\dfrac{n}{p_2}\) 个 \(p_2\) 倍数， 根据容斥原理，可得 \([1, n]\) 中不能被 \(p_1, p_2\) 整除的数共有：
归纳可得，即对于 \(n\) 的所有质因数 \(p_1, p_2, \cdots,p_m\) 可得：
\[\frac{\phi(n)} {n} = \prod_{i = 1} ^ m(1 - \frac 1 {p_i}) \]证明2：
若 \(n = 1\) ，则 \(\phi(1) = 1\) ;
若 \(n\) 是质数， 则 \(\phi(n) = n - 1\) ，因为质数与小于它的每个正整数都互质；
若 \(n = p^k\) ( \(p\) 为质数， \(k\in N ^ *\) )，则小于等于 \(n\) 的数中，因子包含质数 \(p\) （也就是不存在互质）的数共计 \(p^{k - 1}\) 个， 即 \(p\times1,p\times2, \cdot\cdot\cdot, p \times p^{k - 1}\) ，剩余与 \(p_k\) 互质的数为：
\[\phi(p^k) = p^k - p^{k - 1} = p^k(1 - \frac 1 p) \]若 \(n = p \cdot q\) ，而且 \(p, q\) 互质，有 \(\phi(n) = \phi(p\cdot q) = \phi(p) \cdot \phi(q)\)（欧拉函数是积性函数）[积性函数指对于所有互质的整数 \(a\) 和 \(b\) 有性质 \(f(a\cdot b) = f(a) \cdot f(b)\) 的数论函数]
证明：将 \(\left[1, p\times q\right]\) 的值排列如下
\[\begin{matrix} &1 &2 &\cdots &i &\cdots &q\\ &1 + q &2 + q &\cdots &i + q &\cdots &2q\\ &1 + 2q &2 + 2q &\cdots &i + 2q &\cdots &3q\\ &\vdots &\vdots &\ddots &\vdots &\ddots &\vdots\\ &1 + jq &2 + jq &\cdots &i + jq &\cdots &(j + 1)q\\ &\vdots &\vdots &\ddots &\vdots &\ddots &\vdots\\ &1 + (p - 1)q &2 + (p - 1)q &\cdots &i + (p - 1)q &\cdots &p \end{matrix} \]对于每一行数 \(i + jq\) ，其对 \(q\) 取余的余数为 \([1,2,3,…,q-1,0]\) ，即有 \(\phi(q)\) 个数与 \(q\) 互质；对于每一列数 \(i + jq, j \in [0, p − 1]\) ，由于 \(p, q\) 互质，同理也有 \(\phi(p)\) 个数与 \(p\) 互质。
对于任一与 \(p\times q\) 互质的数 \(a(a < p \times q)\)，若 \(a\) 与 \(p\) 互质，\(a\) 与 \(q\) 互质，则 \(a\) 属于这 \(\phi(q)\) 行、\(\phi(p)\)列中的某一数。这样的 \(a\) 总共有 \(\phi(p) \cdot \phi(q)\) 个。即
\[\phi(p\cdot q) = \phi(p) \cdot \phi(q) \]通式：
对于任意一个非 \(1\) 的正整数，都可写成一系列质数之积：\(n = p_1^{k_1}\cdot p_2^{k_2}\cdots p_m^{k_m}\) ( \(p_1, p2, \cdots , p_m\) 都为质数)
由于欧拉函数的积性性质 \(\phi(p\cdot q) = \phi(p) \cdot \phi(q)\) 可得 ：
\[\phi(n) = \phi(p_1^{k_1})\phi(p_2^{k_2})\cdots\phi(p_m ^ {k_m}) \]由式 \(\phi(p^k) = p^k - p ^ {k - 1} = p^k( 1-\dfrac 1 p)\) 可得
\[\begin{aligned} \phi(n) &= p_1 ^ {k_1}(1- \dfrac {1}{p_1})p_2 ^ {k_2}(1- \dfrac {1}{p_2})\cdots p_m ^ {k_m}(1- \dfrac {1}{p_m})\\ &=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}(1 - \dfrac{1}{p_1})(1 - \dfrac{1}{p_2})\cdots(1 - \dfrac{1}{p_m}) \end{aligned} \]即 \(\phi(n) = n\cdot\prod_{i = 1} ^ m(1 - \dfrac{1}{p_i})\)
欧拉函数性质：
· \(\phi(a\cdot b) = \phi(a) \cdot \phi(b)
\cdot \dfrac{d}{\phi(d)}, d = \gcd(a, b)\)
· \(\left[1, n\right]\) 中所有与 \(n\) 互质的数之和为 \(\dfrac{\phi(n) \times n}{2}\)
· \(\sum_{i|n}\phi(i) = n\)
·
\(\phi(n) = \begin{cases}
\phi(\dfrac{n}{p}) \times p, &p | n, p^2 \ n\\
\phi(\dfrac{n}{p}) times (p - 1), &p | n,p^2 \nmid n
\end{cases}\)