算数基本定理:修订间差异

来自吾萌百科
无编辑摘要
 
(未显示同一用户的3个中间版本)
第1行: 第1行:
'''算数基本定理(Fundamental Theorem of Arithmetic)'''即:任何一个大于1的正整数都能被唯一分解为有限个素数的乘积,可写作:
'''算数基本定理(Fundamental Theorem of Arithmetic)'''即:任何一个大于1的正整数都能被唯一分解为有限个[[素数]]的乘积,可写作:


<math>N = \prod_{i=1}^n p_i^{c_i} = {p_1}^{c_1}{p_2}^{c_2}\cdots{p_n}^{c_n}</math>
<math>N = \prod_{i=1}^n p_i^{c_i} = {p_1}^{c_1}{p_2}^{c_2}\cdots{p_n}^{c_n}</math>


其中 <math>c_i</math> 都是正整数,<math>p_i</math> 都是素数,且满足 <math>p_1<p_2<\cdots <p_n</math>
其中 <math>c_i</math> 都是正整数,<math>p_i</math> 都是[[素数]],且满足 <math>p_1<p_2<\cdots <p_n</math>


== 实现 ==
== 实现 ==
结合素数判定的“试除法”和素数筛选的“Eratosthenes筛法”,我们可以扫描 <math>2 \backsim \lfloor \sqrt N \rfloor</math> 的每个数d,若d能整除N,则从N中除掉所有的因子d,同时累计除去的d的个数。
结合[[素数]]判定的“试除法”和素数筛选的“Eratosthenes筛法”,我们可以扫描 <math>2 \backsim \lfloor \sqrt N \rfloor</math> 的每个数d,若d能整除N,则从N中除掉所有的因子d,同时累计除去的d的个数。


因为一个合数的因子一定在扫描到这个合数之前就从N中被除掉了,所以在上市u过程中能整除N的一定是素数。最终就得到了分解素因数的结果,易知时间复杂度为 <math>O(\sqrt N)</math>。
因为一个合数的因子一定在扫描到这个合数之前就从N中被除掉了,所以在上述过程中能整除N的一定是[[素数]]。最终就得到了分解素因数的结果,易知时间复杂度为 <math>O(\sqrt N)</math>。


特别的,若N没有被任何 <math>2 \backsim \lfloor \sqrt N \rfloor</math> 的数整除,则N是素数,无需分解。
特别的,若N没有被任何 <math>2 \backsim \lfloor \sqrt N \rfloor</math> 的数整除,则N是[[素数]],无需分解。


<syntaxhighlight lang="c" line>
<syntaxhighlight lang="c" line>
第17行: 第17行:
void divide(int n) {
void divide(int n) {
m = 0;
m = 0;
for (int i = 2; i < sqrt(n); ++i) {
for (int i = 2; i * i < n; ++i) {
if (n % i == 0) {
if (n % i == 0) {
p[++m] = i;
p[++m] = i;
第33行: 第33行:
}
}
</syntaxhighlight>
</syntaxhighlight>
== 参考资料 ==
# 算法竞赛进阶指南,李煜东,137页
[[Category:数学]]

2022年2月24日 (四) 15:46的最新版本

算数基本定理(Fundamental Theorem of Arithmetic)即:任何一个大于1的正整数都能被唯一分解为有限个素数的乘积,可写作:

[math]\displaystyle{ N = \prod_{i=1}^n p_i^{c_i} = {p_1}^{c_1}{p_2}^{c_2}\cdots{p_n}^{c_n} }[/math]

其中 [math]\displaystyle{ c_i }[/math] 都是正整数,[math]\displaystyle{ p_i }[/math] 都是素数,且满足 [math]\displaystyle{ p_1\lt p_2\lt \cdots \lt p_n }[/math]

实现

结合素数判定的“试除法”和素数筛选的“Eratosthenes筛法”,我们可以扫描 [math]\displaystyle{ 2 \backsim \lfloor \sqrt N \rfloor }[/math] 的每个数d,若d能整除N,则从N中除掉所有的因子d,同时累计除去的d的个数。

因为一个合数的因子一定在扫描到这个合数之前就从N中被除掉了,所以在上述过程中能整除N的一定是素数。最终就得到了分解素因数的结果,易知时间复杂度为 [math]\displaystyle{ O(\sqrt N) }[/math]

特别的,若N没有被任何 [math]\displaystyle{ 2 \backsim \lfloor \sqrt N \rfloor }[/math] 的数整除,则N是素数,无需分解。

int c[MAX_N], p[MAX_N];
int m;
void divide(int n) {
	m = 0;
	for (int i = 2; i * i < n; ++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;
	}
}

参考资料

  1. 算法竞赛进阶指南,李煜东,137页