数论学习笔记（筛质数和约数篇一）

来学数论！本文介绍质数和约数以及各种对应常见应用。

质数判定

试除法

枚举二到 $\sqrt{n}$ 的所有数 $i$，若 $n$ 能被 $i$ 整除，则 $n$ 不是质数。
否则则是质数。
为什么只需要枚举到 $\sqrt{n}$？
因为如果有一个数 $i > \sqrt{n}$ ，且 $i|n$（“ | ”表示 “ 整除 ” ，即 $n \bmod{i}=0$），那么 $\dfrac{n}{i}$ 一定整除 $n$，而 $i > \sqrt{n}$，则 $\dfrac{n}{i}$ 一定小于 $\sqrt{n}$，那么在从小到大的枚举中就已经判断出 $n$ 能被一个数整除，则无需再继续枚举。所以只需要枚举到 $\sqrt{n}$。

质数筛选

埃氏筛法

从二开始小到大枚举每一个数，当枚举到当前数位质数时（即该数未被标记过），则将该数及其所有倍数标记。
一遍跑下来以后，没有被标记的数即为质数。
代码懒得打

时间复杂度

由于在筛质数的过程中会有一些合数被重复标记，时间复杂度非线性（但非常接近线性）。
时间复杂度为 $O \left ( N log^{2} N \right )$。

线性筛

通过保证每个数只能被它的最小质因子筛去，而达到让每个数只被筛去一遍，使时间复杂度达到线性。
代码中解释。

void get_primes( int x ) 
{   //线性筛本体
	//primes[] 数组存质数
	for(int i = 2; i <= x; i ++) 
	{
		if( ! st[i] ) primes[ cn ++ ] = i;   //当前数未被标记过（即当前数为质数），将其标记
		for(int j = 0; primes[j] <= x / i; j ++) 
		{   //从小到大枚举每一个质数
			st[ primes[j] * i ] = 1;  //将每一个质数的倍数标记
			if( i % primes[j] == 0 ) break;   
			//如果 i 能被当前质数整除了，说明当前质数为 i 的最小质因子
			//此时就应跳出循环
			//因为 i*primes[j+1] 这个数的最小质因子也是primes[j]而不是primes[j+1]
		}
	}
}

主要就是一个 if ( i % primes[j] == 0 ) break; 该怎么理解。
设当前质数为 $p\_{j}$，下一个质数为 $p\_{j+1}$。
当枚举到 $p\_{j}$ 时，因为 $p\_{j}|i$，所以有 $p\_{j}|i \times p\_{j+1}$
所以 $p\_{j}$ 为 $i \times p\_{j+1}$ 的最小质因数（ $i \times p\_{j+1}$ 在后面的循环中会被 $p\_{j}$ 筛去）。
而我们要保证每个数只被它的最小质因数筛去，所以应该退出循环。

时间复杂度

由于每个数只被筛了一次，所以算法是线性的，时间复杂度为 $O( N )$。

质因数分解

算数基本定理

任意一个大于 1 的正整数都能被分解为有限个质数的乘积，写作：
$N=p\_{1}^{c\_{1}}p\_{2}^{c\_{2}}...p\_{m}^{c\_{m}}$
其中 $c\_{i}$ 都是正整数，$p\_{i}$ 都是质数，且满足 $p\_{1}$ < $p\_{2}$ < … < $p\_{m}$

试除法

懒得讲

约数

约数个数

求一个数的约数个数。
有如下定理：
正整数 $N$ 满足：
$N=p\_{1}^{c\_{1}}p\_{2}^{c\_{2}}...p\_{m}^{c\_{m}}$
则 N 的正约数个数为
$\left (c\_{1}+1\right ) \times \left (c\_{2}+1\right ) \times ...\times \left (c\_{m}+1\right )$
证明如下：
对于 $N$ 的一个质因数 $p\_{1}$ ，它可以选择 0 个， 1 个， 2 个… $c\_{1}$个，共 $\left ( c\_{1} +1 \right )$ 种选法；
同样的，对于其他的质因数也有 $\left ( c\_{2} +1 \right )$，$\left ( c\_{3} +1 \right )$ … $\left ( c\_{m} +1 \right )$种选法。
则总共能构成的排列有 $\left (c\_{1}+1\right ) \times \left (c\_{2}+1\right ) \times ...\times \left (c\_{m}+1\right )$ 种，即有 $\left (c\_{1}+1\right ) \times \left (c\_{2}+1\right ) \times ...\times \left (c\_{m}+1\right )$ 个约数。
代码懒得打

约数之和

有如下定理：
正整数 $N$ 满足：$N=p\_{1}^{c\_{1}}p\_{2}^{c\_{2}}...p\_{m}^{c\_{m}}$

则 N 的所有正约数之和为
$\left(1+p\_{1}+p\_{1}^{2}+\ldots+p\_{1}^{c\_{1}}\right) \times\left(1+p\_{2}+p\_{2}^{2}+\ldots+p\_{2}^{c\_{2}}\right) \times \ldots \times\left(1+p\_{m}+p\_{m}^{2}+\ldots+p\_{m}^{c\_{m}}\right)$
证明如下：
由于 $N$ 的约数个数为 $\left (c\_{1}+1\right ) \times \left (c\_{2}+1\right ) \times ...\times \left (c\_{m}+1\right )$，由乘法原理可得其正约数之和为 $\left(1+p\_{1}+p\_{1}^{2}+\ldots+p\_{1}^{c\_{1}}\right) \times\left(1+p\_{2}+p\_{2}^{2}+\ldots+p\_{2}^{c\_{2}}\right) \times \ldots \times\left(1+p\_{m}+p\_{m}^{2}+\ldots+p\_{m}^{c\_{m}}\right)$。
代码照样懒得打

最大公约数

首先讲一下同余

同余

若 $a \bmod{m}=b \bmod{m}$ ，则称 $a$ 与 $b$ 同余，写作 $a \equiv b \pmod{m}$

性质

可以自己百度一下。
主要就几个。
这里用到的有：满足基本加减乘除运算（除去的数必须与 $m$ 互质）

互质

当 $a \equiv 1 \pmod{m}$ 时，我们称 $a$ 与 $m$ 互质。
即 $a$ 与 $m$ 的最大公约数为 1 。

计算最大公约数

我们用 $\gcd(a,b)$ 表示 $a$ 与 $b$ 的最大公约数。

九章算术 · 更相减损术

不是很常用，这里不讲了。
我懒

欧几里得算法

又称 辗转相除法 。
如下：
$\forall a$，$b \in N$ ，$b \ne 0$，$\gcd(a,b)=\gcd(b,a \bmod{b})$
证明如下：
若 $a < b$，则 $\gcd(b,a \bmod{b})= \gcd(b,a)= \gcd(a,b)$
若 $a \ge b$，不妨设 $a = qb + r$，其中 $0 ≤ r < b$。显然 $r = a \bmod {b}$。对于 $a$，$b$ 的任意公约数 $d$，因为 $d|a$，$d|bq$，所以 $d|(a - bq)$，即 $d|r$，因此 $d$ 也是 $b$，$r$ 的公约数。反之亦然。故 $a$，$b$ 的公约数集合与 $b$，$a \bmod {b}$ 的公约数集合相同，故它们的最大公约数也相等。
代码：

int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }

就一行，短吧。
剩下的知识点以后再说吧 （下辈子）。