质数，约数，欧拉函数，快速幂

---

质数

素数计数函数：

小于或等于$x$的素数的个数，用$\pi (x)$表示。随着$x$的增大，有近似结果：
KaTeX parse error: Undefined control sequence: \textasciitilde at position 8: \pi(x) \̲t̲e̲x̲t̲a̲s̲c̲i̲i̲t̲i̲l̲d̲e̲ ̲\frac{x}{ln(x)}。

质数的判定：

若$x$是$a$的约数，那么$\frac{a}{x}$也是$a$的约数。

对于每一对约数，我们只需检验其中的一个。我们每次检查每对中较小的一个。不难发现，所有这些较小的数都在区间$[1,\sqrt{a}]$ 中。

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

分解质因数：

由算数基本定理可知，大于1的正整数都可以被写成若干个质数相乘。

由于因数是成对分布的，所以$n$中所有质因数被分成两个区间：$[2,\sqrt{n}]$，$[\sqrt{n}+1,n]$。

并且，大于$\sqrt{n}$的质因数最多只有一个。所以最后如果$n>1$，那么$n$就是大于$\sqrt{n}$的质因子。

我们在枚举$i$的时候，将$n$的因数中与$i$有关的全部筛掉。所以当if(n % i) == 0成立时，总有$i$是质数。

unordered_map<int, int> primes;
void get_divisors(int n) {for(int i = 2; i <= n / i; i ++) {if(n % i == 0) {while(n % i == 0) {primes[i] ++;n /= i;}}}if(n > 1) primes[n] ++;
}

素数筛法

我们想要知道小于等于$n$有多少个素数，显然我们不能满意对所有小于等于$n$的数一一判断。

埃氏筛法：

对于每一个合数，我们都用质数把它筛掉。

当第$p$个数没被筛掉时，就证明从$2$到$p-1$中没有第$p$个数的约数。如果第$p$个数是合数，则它一定能被从$2$到$p-1$中的质数筛掉。所以第$p$个数一定是质数。

在埃氏筛法中，合数可能被多次筛去。我们想要一个合数被筛掉一次，那么每次筛就要用最小质因数筛。

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

线性筛法：

我们每次使用最小质因数筛掉合数。

我们讨论$i\cdot primes[j]$是否是最小质因数：

• 当i % primes[j] == 0时，由于我们是从小到大枚举的质数，所以$primes[j]$一定是$i$的最小质因子。所以，$primes[j]$是$i\cdot primes[j]$的最小质因子。

• 当i % primes[j] != 0时，由于我们是从小到大枚举的质数，所以$primes[j]$一定小于$i$的最小质因子。所以，$primes[j]$是$i\cdot primes[j]$的最小质因子。

if(i % primes[j] == 0) break;保证了我们每次都用最小质因子筛数。

int primes[N];
bool st[N];
int cnt = 0;
void get_primes(int n) {for(int i = 2; i <= n / i; 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;}}
}

---

约数

最大公约数：

我们通过证明可以得到$gcd(a,b)=gcd(b,amodb)$

证明过程略。

所以有以下递归写法：

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

另外，对于 C++17，我们可以使用<numeric>中的gcd与lcm来求最大公约数和最小公倍数。

如果$a$和$b$满足$gcd(a,b)=1$，我们称$a$和$b$互质。