数学基础——质数

算术基本定理(唯一分解定理)

• 内容 :

• 应用

  • 分解质因数

int cnt,p[N],a[N];
void div(ll n) {
	int cnt = 0;
	for(int i = 2;i*i <= n; ++i) {
		if(n%i == 0) {
			p[++cnt] = i;
			while(n%i == 0) {
				n /= i,++a[cnt];
			}
		}
	}
	if(n > 1) {
		p[++cnt] = n;
 		++a[cnt];
 	}
 }

• 求约数个数

  约数个数函数

[ d(n) = prod (a_i+1) ]

• 求约数和

  约数和函数

  [sigma(n) = prod(sum_{j = 0}^{a_i}p^j) = prod frac{1-p_i^{a_i+1}}{1-p_i} ]

线性筛

• 原理 : 保证每个数只会被其最小的质因子筛去

• 实现 : 设(v_i)表示数(i)的最小质因子,依次枚举每个数,若(v_i == 0)(即未被筛),说明其是一个质数

  接着依次枚举小于(v_i)的已经筛出的质数(设为(p)),可知(p)为合数(p*i)的最小质因数((p < v_i))

  注意(p*i)不能超过(n)

int v[N],p[N],p_cnt;
void primes(int n) {
	for(int i = 2;i <= n; ++i) {
		if(!v[i]) v[i] = i,p[++p_cnt] = i;
		for(int j = 1;j <= p_cnt; ++j) {
			if(p[j] > v[i] || p[j]*i > n) break;
			v[p[j]*i] = p[j];
		}
	}
}