o.O

一、\(O(\sqrt{n})\) 判断质数

枚举 \(\left[2,\sqrt{n}\right]\) 中的数，判断是否能整除 \(n\) ，如果都没有则返回 \(true\)。

为什么不用枚举 \(\sqrt{n}\) 以上的数：
假设有一个数 \(a\in\left[\sqrt{n},n\right]\) 是 \(n\) 的约数，那么显然 \(\lfloor \dfrac{n}{a} \rfloor\) 也是 \(n\) 的约数，而 \(\lfloor \dfrac{n}{a} \rfloor\) 必然是小于 \(\sqrt{n}\) 的，在之前就已经被检查过了。

bool isprime(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i)	return false;
	}
	return true;
}

二、质因数分解

用一个 \(vector\) 存储质因数，遍历 \(\left[2,n\right]\) 中的所有数，检查是否是 \(n\) 的约数，如果是则反复除至 \(n\) 的因子不含有当前枚举的数。

为什么遍历的是所有的数，筛出来的却都是质数因数：
假设 \(n\) 有一个合数约数 \(x\)，那么 \(x\) 本身还可以写成若干个小于 \(x\) 的质数相乘，而这些小于 \(x\) 的数已经在之前筛过了。

vector<int> p;
void work(int x){
	for(int i=2;i<=x;i++){
		while(x%i==0){
			p.emplace_back(i);
			x/=i;
		}
	}
}

三、算术基本定理

对于所有的大于1的整数 \(a\) 都有：

事实上就是分解质因数，把 \(a\) 分解成 \(k\) 个质数的若干次幂之和。
代码基本同分解质因数。

vector<int> p,c;
void work(int x){
	for(int i=2;i<=x;i++){
		int cnt=0;
		while(x%i==0){
			if(!cnt)	p.emplace_back(i);
			x/=i,cnt++;
		}
		if(cnt)	c.emplace_back(cnt);
	}
}
//k=p.size()或c.size()

四、埃氏筛质数

筛除每个质数的倍数，剩下的即为质数。

五、欧拉筛质数

欧拉筛相对埃氏筛的进步就是最大限度地减少了重复筛出合数的情况。

1.外层枚举一个数 \(i\)

for(int i=2;i<=n;i++){

2.如果在这之前 \(i\) 没有被标记为合数（即 \(c_i=1\)），就将 \(i\) 加入质数集合

if(!c[i]) p.emplace_back(i);

3.然后枚举所有的已知质数，作为一个“基底”\(base\)。

for(int base:p){

4.先来检查 \(base\) 的 \(i\) 倍是否已经超出了 \(n\)，如果是直接跳出内层枚举

if(i*base>n) break;

5.将 \(base\) 的 \(i\) 倍标记为合数

c[base*i]=1;

6.如果 \(i\) 是 \(base\) 的倍数，跳出内层枚举防止重复筛除

if(i%base==0) break;

当 \(i\) 是 \(base\) 的倍数时就跳出内层，为什么能防止重复：
还是记内层枚举到的质数为 \(base\)。
首先要理解到 \(i\) 的含义在枚举内层时发生了转变。
——在外层时，\(i\) 的含义就是要被检查是否为质数的一个数
——在内层时，\(i\) 成为了“倍数”，表示现在要标记 \(base\) 的 \(i\) 倍为合数
注意到并不是筛除 \(i\) 的 \(base\) 倍，而是筛除 \(base\) 的 \(i\) 倍！
然后来讨论为什么 \(i\) 是 \(base\) 的倍数后面就会重复。
我们设 \(i=a*base\)，其中 \(a\) 是不为 \(1\) 的整数。
假设我们当前已经满足i%base==0，但不跳出，就会枚举到下一个质数，记其为 \(base'\)。
这样我们就会尝试标记 \(base'\) 的 \(i\) 倍为合数。
虽然它确实是合数，但它也能被 \(base\) 的其他倍筛去，这就导致了重复。
具体地，我们设当前试图筛去的数为 \(k\)，即 \(k=base'*i\)。
由于之前有 \(i=a*base\)，所以 \(k\) 也能写成 \(k=base*(a*base')\)
这也就意味着，目前的 \(k\) 也会在外层 \(i\) 枚举到 \(a*base'\)、内层再次枚举到 \(base\) 时作为“\(base\) 的 \(a*base'\) 倍”被筛去
举个例子，如果 \(i=4,base=2\)，按理说就应该跳出，若不跳出枚举到下一个 \(base'=3\)，试图筛去的 \(k=base'*i=3*4=12=2*6=base*6\)

如何保证在 \(i\) 枚举到 \(a*base'\) 时，内层循环不会在再次枚举到 \(base\) 之前跳出：
注意到 \(i=a*base\) 中，\(a\) 的最小因子一定是不小于 \(base\) 的。
如果 \(a\) 有小于 \(base\) 的因子，那么内层循环一定会在枚举到 \(base\) 之前就跳出
又因为 \(base'\) 显然大于 \(base\)
所以 \(a*base'\) 的最小因子也是大于 \(base\) 的，这就意味着当 \(i\) 枚举到 \(a*base'\)时，其内层循环在枚举到 \(base\) 之前不会存在满足i%base==0这个语句的情况，因为那当且仅当 \(a*base'\) 有小于 \(base\) 的因数时才有可能发生。

欧拉筛整体代码

bool c[MAXN];
vector<int> p;
void work(int n){
	for(int i=2;i<=n;i++){
		if(!c[i])	p.emplace_back(i);
		for(int base:p){
			if(i*base>n)	break;
			c[base*i]=1;
			if(i%base==0)	break;
		}
	}
}

七、gcd,lcm,exgcd

gcd与exgcd的具体证明在之前的文章。
这里给出 \(\gcd(a,b)*\operatorname{lcm}(a,b)=a*b\) 的证明。

先考虑证明互质的两数 \(p,q\) 的最小公倍数为 \(p*q\)
由于显然 \(p*q\) 是 \(p,q\) 的公倍数，设其不是最小公倍数
则存在一个整数 \(k\)，使得 \(\dfrac{p*q}{k}\) 仍为整数且是 \(p\) 和 \(q\) 的倍数
因为是 \(p\) 的倍数，则 \(\dfrac{\dfrac{p*q}{k}}{p}=\dfrac{p*q}{p*k}=\dfrac{q}{k}\) 为整数
因为是 \(q\) 的倍数，则 \(\dfrac{\dfrac{p*q}{k}}{q}=\dfrac{p*q}{q*k}=\dfrac{p}{k}\) 为整数
这意味着 \(\gcd(p,q)=k\) 因为 \(p=\dfrac{p}{k}*k,q=\dfrac{q}{k}*k\) 而 \(\dfrac{p}{k},\dfrac{q}{k}\) 均为整数，与 \(p,q\) 互质矛盾，故互质的两数 \(p,q\) 的最小公倍数为 \(p*q\)

再证明 \(\gcd(a,b)*\operatorname{lcm}(a,b)=a*b\)
记 \(\gcd(a,b)=g\)，则\(a=a'g,b=b'g\)
显然此处 \(\gcd(a',b')=1\)，否则 \(\gcd(a,b)\) 应为 \(g*\gcd(a'*b')\)
于是我们知道 \(\operatorname{lcm}(a',b')=a'*b'\)
又注意到 \(\operatorname{lcm}\) 满足结合律，即 \(\operatorname{lcm}(ac,bc)=\operatorname{lcm}(a,b)*c\)，证明显然
又因为 \(\operatorname{lcm}(a,b)=\operatorname{lcm}(a,b)\)
所以 \(\operatorname{lcm}(a,b)=\operatorname{lcm}(a'g,b'g)=\operatorname{lcm}(a',b')*g=a'*b'*g\)
两边同乘 \(g\) 得 \(g*\operatorname{lcm}(a,b)=a'*g*b'*g\)
由一开始的三个定义 \(\gcd(a,b)=g,a=a'g,b=b'g\) 替换得
\(\gcd(a,b)*\operatorname{lcm}(a,b)=a*b\)

给出三个算法的代码

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b){
	return a*b/gcd(a,b);
}
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
	}else{
		exgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
}

TBC