【算法竞赛进阶指南】素数

【模板向】主要记录证明和模板,用于忘记时查阅

Part1 质数判定

$$\text{若T} \mid \text{N,则T}\in[2,\sqrt{N}]$$ 反证法易证,就有试除法判断素数

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

Part2 埃氏筛(Eratosthenes)

只需要枚举数x的倍数,这些倍数都不是素数,筛去即可,这里有两处优化:

• 任意合数可以跳过
• $2x$~$x(x - 1)$可以被跳过,即直接从$x^2$开始筛
• $x$的系数$k$最大值为$n/x$

时间复杂度$O(NloglogN)$

void primes(int n){
	memset(v, 0, sizeof v);
	for(int i = 2; i <= n; i ++){
		if(v[i]) continue;
		cout << i << endl;
		for(int j = i; j <= n / i; j ++)
			v[j * i] = 1;
	}
}

Part3线性筛

使每一个合数都只被最小质因数筛,设v数组储存最小质因数,则有 $$\text{对于质数p}\le v_{i},\text{有p是p*i的最小质因数}$$ 证明:假设存在k是更小质因子 $\iff k<p$
$$k|i \text{则有} k \ge v_{i} \ge p$$ $$\text{矛盾，得证}$$ 借助该性质即可使每个素数只被筛一次,完成O(n)线性筛。

int v[N], prime[N], m, n;
void primes(int n){
	memset(v, 0, sizeof v);
	m = 0;
	for(int i = 2; i <= n; i ++){
		if(!v[i]) { v[i] = i; prime[++ m] = i; }
		for(int j = 1; j <= m; j ++){
			if(prime[j] > v[i] || prime[j] > n / i) break;
			v[prime[j] * i] = prime[j];
		}
	}
}

Part4质因数分解

算数基本定理

$$N=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$$

试除法

用$2$~$\sqrt{N}$的每一个数去除去所有因子。特别地, 若$N$没有被任何一个数整除则$N$是素数.

void divide(int n){
	m = 0;
	for(int i = 2; i <= n / i; i ++)
		if(n % i == 0){
			p[++m] = i, c[m] = 0;
			while(n % i == 0) n /= i, c[m] ++;
		}
	if(n > 1) p[++m] = n, c[m] = 1;
}