1、质数：在大于 $1$ 的整数中，如果只包含 $1$ 和本身这两个约数，就被称为质数，或者叫素数。

（1）质数的判定——试除法

bool is_prime(int n)
{
	if (n < 2) return false;
	for (int i = 2; i < n; i ++ )
		if (n % i == 0)
			return false;
	return true;	
}

上述代码时间复杂度为 $O(n)$，所以考虑优化。

有性质：若 $d|n$，则 $\frac{n}{d}|n$，比如 $n=12$，$d$ 可以取 $1, 12$，$2, 6$，$3, 4$，发现 $d$ 和 $\frac{n}{d}$ 都是成对出现的。

因此在枚举时，可以只枚举每一对中较小的那一个。即满足 $d≤\frac{n}{d}→d^2≤n→d≤\sqrt{n}$，则 $d$ 只需要枚举到 $\sqrt{n}$，时间复杂度就可以从 $O(n)$ 降到 $\sqrt{n}$，这是一个质的飞跃。

有些小朋友可能喜欢用下面的写法，但因 sqrt(n) 在每次调用时太慢，故不推荐。

bool is_prime(int n)
{
	if (n < 2) return false;
	for (int i = 2; i <= sqrt(n); i ++ )
		if (n % i == 0)
			return false;
	return true;	
}

也有的小朋友喜欢用下面的写法：

bool is_prime(int n)
{
	if (n < 2) return false;
	for (int i = 2; i * i <= n; i ++ )
		if (n % i == 0)
			return false;
	return true;	
}

这也是不推荐的。因为当 $n=2147483647$ 时，前一次算 $i^2≤n$ 正常，但下一次算就有可能 $(i+1)^2>n$，有溢出风险，溢出后 $i^2$ 就变成一个负数，会影响答案的判断，所以推荐用下面的写法：

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;	
}

时间复杂度 $O(\sqrt{n})$

（2）分解质因数——试除法

思路：从小到大枚举 $n$ 的所有的因数

void divide(int n)
{
	for (int i = 2; i <= n; i ++ )
		if (n % i == 0)
		{
			int s = 0;
			while (n % i == 0)
			{
				n /= i;
				s ++ ;	
			}
			printf("%d %d\n", i, s);
		}	
}

$Q$：为什么不从小到大枚举所有质因数？枚举所有因数不是会有合数吗？

$A$：$n=P_1^{α_1}···P_k^{α_k}$，当枚举到 $i$ 时，就意味着已经把 $2$ ~ $i-1$ 中的所有质因子都除干净了，即 $n$ 当中不包含任何一个 $2$ ~ $i-1$ 中的质因子了，$n$ 是 $i$ 的倍数并且 $i$ 中也不包含 $2$ ~ $i-1$ 中的质因子，因此 $i$ 一定是质数。

时间复杂度：当 $n$ 是质数时，最坏会枚举到 $O(n)$。

优化：由性质（$n$ 中最多只包含一个大于 $\sqrt n$ 的质因子）。

证明：因为如果有两个，它两乘一块一定大于 $n$，矛盾。

所以只需要枚举出 $≤\sqrt n$ 的质因子即可。最后只需单独处理下大于 $\sqrt n$ 的质因子就可以了。

void divide(int x)
{
	for (int i = 2; i <= n / i; i ++ )
		if (n % i == 0)
		{
			int s = 0;
			while (n % i == 0)
			{
				n /= i;
				s ++ ;	
			}
			printf("%d %d\n", i, s);
		}
	if (n > 1) printf("%d %d\n", n, 1);
}

时间复杂度就可以有效地从 $O(n)$ 降低到 $\sqrt n$。

但不一定是 $\sqrt n$，比如当 $n=2^k$ 时，i = 2 时就会直接进来把 $2$ 除干净，$n$ 就等于 $1$ 结束了，时间复杂度是 $O(\log n)$，最坏是 $O(\sqrt n)$，所以是介于 $O(\log n)$ 到 $O(\sqrt n)$ 之间的，平均情况来看是比试除法判断质数要快的。

（3）质数筛法

思路：从前到后把每一个数的倍数删掉。这样筛过之后剩下的数就都是质数。

2 3 4 5 6 7 8 9 10 11 12

原理：对于任何一个数 $P$，如果它没有被删掉，就意味着 $2$ ~ $P-1$ 中没有任何一个数把 $P$ 删掉，说明 $P$ 不是 $2$ ~ $P-1$ 中任何一个数的倍数，即 $2$ ~ $P-1$ 中不存在任何一个数是 $P$ 的约数，所以说 $P$ 就是一个质数。

朴素筛法：

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
		{
			primes[cnt ++ ] = i;
		}
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
}

时间复杂度：$\frac{n}{2}+\frac{n}{3}+···\frac{n}{n}=n(\frac{1}{2}+\frac{1}{3}+···\frac{1}{n})$，由调和级数$\lim\limits_{n\rightarrow\infty}1+\frac{1}{2}+\frac{1}{3}+···\frac{1}{n}=\ln n+c$，欧拉常数$c≈0.577$ 是一个无限不循环小数，所以时间复杂度 $≈n\ln n$，即 $n\log_e n<n\log_2 n$，所以算法的复杂度可以记为 $O(n\log n)$。

优化：并不需要把每一个数的倍数删掉，只需要把所有质数的倍数删掉就可以了。

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
		{
			primes[cnt ++ ] = i;
			for (int j = i + i; j <= n; j += i) st[j] = true;
		}
    }
}

原理：假如按原来的筛法筛的时候，留下了一个数 $P$，说明 $P$ 是一个质数，其实并不需要把 $2$ ~ $P-1$ 全部枚举一遍判断是不是 $P$ 的倍数。而只需要把 $2$ ~ $P-1$ 中的质数判断一下就可以了，只需要知道 $2$ ~ $P-1$ 中的所有质数不是 $P$ 的约数的话，那么 $P$ 就是一个质因数，所以说在筛的时候只需要把质数的倍数筛掉就可以了，当一个数不是质数的时候，我们就不需要筛掉它所有的倍数。

此时时间复杂度粗略地估计下：之前 $1+\frac{1}{2}+\frac{1}{3}+···\frac{1}{n}$，只需要算 $1$ ~ $n$ 直接所有质数的调和级数就可以了。由质数定理：$1$ ~ $n$ 之间有 $\frac{n}{\ln n}$ 个质数，所以 $n(\frac{1}{2}+\frac{1}{3}+···\frac{1}{n})≈n\ln n$，$\frac{n\ln n}{\ln n}=O(n)$，但这是一个粗略估计，真实的时间复杂度是 $O(n\log \log n)$，也就是说 $1+\frac{1}{2}+\frac{1}{3}+···\frac{1}{n}$ 这个调和级数里如果只算质数项的话，它的大小大概是 $\log \log n$。

$\log \log n$ 到底有多小呢？当 $n=2^{32}$ （无符号整数最大值时），$\log n=32$，$\log \log n=5$，所以 $\log \log n$ 基本上和 $n$ 是一个级别的。

此优化过的筛法是一个埃及人发明的，因此被称为埃氏筛法。时间复杂度 $O(n\log \log n)$。

线性筛法（欧拉筛）：

核心思路：$i$ 只会被它的最小质因子筛掉。

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

时间复杂度：当 $n=10^6$ 时，埃氏筛法和线性筛法差不多，但 $n=10^7$ 时，线性筛法会将近快一倍。

原理：为什么是线性的？

正确性 $1$：为什么只会被它的最小质因子筛掉？

1、i % pj == 0：pj 一定是 i 的最小质因子，pj 也一定是 pj * i 的最小质因子。

2、i % pj != 0：pj 一定小于 $i$ 的所有质因子，pj 也一定是 pj * i 的最小质因子。

综上，一定有 pj 是 pj * i 的最小质因子，所以我们筛的每一个数 st[primes[j] * i] = true; 一定是用的这个数的最小质因子去筛它。

正确性 $2$：合数为什么一定会被删掉？

因为对于一个合数 x，它一定是存在一个最小质因子的，假设 pj 是 x 的最小质因子，所以当 i 枚举到 x 的时候一定会先枚举到 x / pj，那么当 i 枚举到 x 的时候就一定会在内层循环中删掉，所以说任何一个合数都会被删掉。

而且我们筛的时候只用最小质因子来筛，并且每一个数都只有一个最小质因子，所以说每个数只会被筛一次，所以它是线性的。

还有一点要说明，有的同学可能想写

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; j < cnt && primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

这个没有必要，因为如果 i 是合数的话，当 pj 枚举到 i 的最小质因子时，就一定会停下来，$i$ 的最小质因子又一定小于 i；当 i 是质数的时候，pj 等于 i 的时候也会停下来，所以无论如何 j 都会在大于等于 cnt 之前停下来，所以不需要加 j < cnt。

例如 $9$ 如果用朴素筛法就会在 $3$ 的时候被筛掉，如果用线性筛的话，就会在 i = 3, pj = 3 的时候被筛掉。

现实应用的时候线性筛法用的多一点，埃氏筛法的思想比较重要。很多算法我们可能不是用埃氏筛法来求素数，而是用这种思想来解决其他问题。

2、约数

（1）试除法求一个数的所有约数

思路：从小到大枚举每一个数，如果能被它整除的话就是约数。

优化：因为 $d|n$，$\frac{n}{d}|n$，因此约数也是成对出现的，所以在枚举的时候只需要枚举较小的约数就可以了，较大的那个约数可以直接算出来。所以只需要枚举到 $d≤\frac{n}{d}$ 就可以了。

vector<int> get_divisors(int n)
{
    vector<int> res;
    for (int i = 1; i <= n / i; i ++ )
        if (n % i == 0)
        {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    sort(res.begin(), res.end());
    return res;
}

时间复杂度：$O(\sqrt n)$。

做数论题的关键是把每一步计算的时间复杂度都算出来，只有每一步计算都不超时的话才可以做。

再考虑下 sort，考虑下一个数的约数个数大概有多少个呢？

如果要求 $1$ ~ $n$ 中每一个数的约数个数，我们用类似于筛法的过程来一个一个看。

1 2 3 ··· n

首先 1 是所有数的约数，其他数是它所有倍数的约数。所以说 $1$ ~ $n$ 中所有约数的个数和 $1$ ~ $n$ 中所有倍数的个数是相同的。

那么倍数的个数有 $n+{\frac{n}{2}}+{\frac{n}{3}}···+{\frac{n}{n}}=n\ln n$ 个，即 $n\log n$ 个，所以 $1$ ~ $n$ 中总共约数个数是 $n\log n$，平均下来看每个数的约数个数就是 $\log n$。

所以前面循环的时间复杂度是 $O(\sqrt n)$，后面 sort 的时间复杂度是 $O(\log n · \log \log n)$，而一般来说$\log n · \log \log n＜\sqrt n$，所以总的时间复杂度是 $O(\sqrt n)$。

（2）约数个数

先要做质因数分解，基于算术基本定理：对于任何一个整数 $N$ 如果它分解完质因数之后的结果是 $N=P_1^{α_1}P_2^{α_2}···P_k^{α_k}$，那么约数个数就是 $(α_1+1)(α_2+1)···(α_k+1)$。

原理：因为 $N$ 的任何一个约数也可以由算术基本定理写成 $d=P_1^{β_1}P_2^{β_2}···P_k^{β_k}$，$0≤β_i≤α_i$。那么 $N$ 的任何一个约数都可以写成上述形式，而且每一项的指数只要不同的话，它的约数就不同，所以说 $N$ 的约数的个数就和 $β_1$ ~ $β_k$ 的取法的个数是一模一样的。即 $N$ 的每一个约数都对应了一个 $β_1$ ~ $β_k$ 的取法，而且每两个不同的取法都对应了 $N$ 的两个不同的约数，因为算术基本定理告诉我们，每个数的因式分解是唯一的，所以只要因式分解不一样，这两个数就不一样，所以 $N$ 的每一个约数都和 $β_1$ ~ $β_k$ 的每个选法是一一对应的。所以选法的个数和约数的个数是相同的。

选法就是一个乘法原理，得约数个数公式 $(α_1+1)(α_2+1)···(α_k+1)$。

小经验：int 范围内，约数个数最多大概是 $1500$ 个。

（3）约数之和

如果 $N=P_1^{α_1}P_2^{α_2}···P_k^{α_k}$，那么约数之和的公式为 $(P_1^0+P_1^1+···+P_1^{α_1})···(P_k^0+P_k^1+···+P_k^{α_k})$。

原理：直接用乘法原理展开此公式，会变成一堆乘积相加的形式 ( ) + ( ) + ··· + ( )。那么从中一个个选的话一共有 $(α_1+1)(α_2+1)···(α_k+1)$ 种选法。每一个乘积都应该是这样的形式 $P_1^{β_1}···P_k^{β_k}$，${β_1}$ 就应该是取遍了 $0$ ~ $α_1$，其中每一项都是一个约数，并且任意两项之间都是不同的，而且总数和约数个数又相同，所以说这个公式其实就是把所有的约数加到一起了。

学数论就和学数学一样，一定要在纸上推一遍公式。

题目：给定 $n$ 个数，$a_1···a_n$，统计一下 $(a_1*a_2*···*a_n)$ 的约数个数，答案对 $10^9+7$ 取模。

思路：先分解质因数 $(a_1*a_2*···*a_n)=P_1^{α_1}P_2^{α_2}···P_k^{α_k}$，先分别把 $a_1···a_n$ 全部分解，然后把每一个数的指数累加在一起就可以了。分解完后直接套公式 $(α_1+1)(α_2+1)···(α_k+1)$。

具体分解时，比如说求出来了 $a_1$ 的某一个质因子 $P_i^{α_i}$，可以用哈希表或者一个 map 把它存下来，map[pi] += a_i，最后 map 就把所有质因数分解的底数和指数存下来了，然后把所有指数 $+1$ 再相乘。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;

    while (n -- )
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto prime : primes) res = res * (prime.second + 1) % mod;

    cout << res << endl;

    return 0;
}

题目：给定 $n$ 个数，$a_1···a_n$，请你输出 $(a_1*a_2*···*a_n)$ 的约数之和，答案对 $10^9+7$ 取模。

思路：先分解质因数，然后代入求和公式即可。

先要算 $(P^0+P^1+···+P^a)$，可以让 t = p * t + 1;

$t=1$;

$=p+1$;

$=p^2+p+1$;

$=P^a+···+1$。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;

    while (n -- )
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto prime : primes)
    {
        LL p = p.first, a = p.second;
        LL t = 1;
        while (a -- ) t = (t * p + 1) % mod;
        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

求和的时候只需要求 $n$ 次就可以了，时间复杂度是 $O(n)$，比快速幂 $O(logn*n)$ 更快，但其实 $(P^0+P^1+···+P^a)$ 有更快 $O(\log a)$ 的做法，基于分治，不是这道题的重点，这道题已经够用了，因为所有的质因子，$a$ 最大是 $\log n$（底数是 $2$ 的话），最多有 $100$ 个整数，所以求和那一步的时间复杂度是 $100*\log n$，已经很小了，没有必要再用快速幂优化。

所以每一步最好都去算一下它的时间复杂度，并不是所有地方都需要用算法去优化，如果某一步对大家算法要求不高的话，直接循环就可以了，只有说这一步是算法瓶颈的时候，才要去考虑对它做优化，没有必要优化不是瓶颈的部分。

（4）求最大公约数：欧几里得算法（辗转相除法）

核心思路：

首先数论里有一些基本的性质：

若 $d|a$，$d|b$，则有 $d|{a+b}$，也能整除 $a$ 的若干倍、$b$ 的若干倍 $d|ax+by$。

那么最大公约数 $(a,b)$ = $(b,a \mod b)$。

原理：$a \mod b=a-\lfloor \frac{x}{b} \rfloor * b$，可记为 $a \mod b=a-c*b$，那么只需证 $(a,b)$ = $(b,a-c*b)$。

因为左边的任何一个公约数 $d$，都有 $d|a$，$d|b$，$d|{a+b}$，左边的任何一个公约数都是右边的一个公约数；从右往左看，因为 $d|b$，$d|a-c*b$，那么就有 $d|a-c*b + c*b$，所以 $d|a$，那么右边的任何一个公约数又是左边的一个公约数，所以这两个公约数的集合是相同的，所以左边的最大公约数就等于右边的最大公约数，所以是成立的。

那么就有了一行代码的模板：

#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}

时间复杂度是：$O(\log n)$。

还有一种更相减损术用的不多，只有在极个别的情况下才会用，即使 $n=2^{64}$，也是很快可以算出来的。