算数基本定理 - 版本历史

Rmolives：/* 实现 */

2022-02-24T07:46:22Z

实现

←上一版本		2022年2月24日 (四) 15:46的版本
第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;

2022年2月22日 (二) 08:56 Rmolives

2022-02-22T08:56:14Z

←上一版本		2022年2月22日 (二) 16:56的版本
第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中被除掉了，所以在上述过程中能整除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>

Rmolives：/* 实现 */

2022-02-22T08:05:37Z

实现

←上一版本		2022年2月22日 (二) 16:05的版本
第8行：		第8行：
	结合素数判定的“试除法”和素数筛选的“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是素数，无需分解。

2022年2月22日 (二) 08:03 Rmolives

2022-02-22T08:03:57Z

←上一版本		2022年2月22日 (二) 16:03的版本
第33行：		第33行：
	}		}
	</syntaxhighlight>		</syntaxhighlight>

			== 参考资料 ==
			# 算法竞赛进阶指南，李煜东，137页
			[[Category:数学]]

2022年2月22日 (二) 08:02 Rmolives

2022-02-22T08:02:49Z

←上一版本		2022年2月22日 (二) 16:02的版本
第6行：		第6行：

	== 实现 ==		== 实现 ==
	结合素数判定的“试除法”和素数筛选的“Eratosthenes筛法”，我们可以扫描 <math>2\~~~{}~~ \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中被除掉了，所以在上市u过程中能整除N的一定是素数。最终就得到了分解素因数的结果，易知时间复杂度为 <math>O(\sqrt N)</math>。

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

	<syntaxhighlight lang="c" line>		<syntaxhighlight lang="c" line>

Rmolives：/* 实现 */

2022-02-22T08:00:59Z

实现

←上一版本		2022年2月22日 (二) 16:00的版本
第6行：		第6行：

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

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

	特别的，若N没有被任何 <math>2\~ \lfloor \sqrt N \rfloor</math> 的数整除，则N是素数，无需分解。		特别的，若N没有被任何 <math>2\~{} \lfloor \sqrt N \rfloor</math> 的数整除，则N是素数，无需分解。

	<syntaxhighlight lang="c" line>		<syntaxhighlight lang="c" line>

2022年2月22日 (二) 08:00 Rmolives

2022-02-22T08:00:43Z

←上一版本		2022年2月22日 (二) 16:00的版本
第6行：		第6行：

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

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

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

	<syntaxhighlight lang="c" line>		<syntaxhighlight lang="c" line>

2022年2月22日 (二) 07:59 Rmolives

2022-02-22T07:59:24Z

←上一版本		2022年2月22日 (二) 15:59的版本
第4行：		第4行：

	其中 <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~\lfloor \sqrt N \rfloor</math> 的每个数d，若d能整除N，则从N中除掉所有的因子d，同时累计除去的d的个数。

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

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

			<syntaxhighlight lang="c" line>
			int c[MAX_N], p[MAX_N];
			int m;
			void divide(int n) {
			m = 0;
			for (int i = 2; i < sqrt(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;
			}
			}
			</syntaxhighlight>

2022年2月21日 (一) 11:52 Rmolives

2022-02-21T11:52:33Z

←上一版本		2022年2月21日 (一) 19:52的版本
第1行：		第1行：
	'''算数基本定理（Fundamental Theorem of Arithmetic）'''即：任何一个大于1的正整数都能被唯一分解为有限个素数的乘积，可写作：		'''算数基本定理（Fundamental Theorem of Arithmetic）'''即：任何一个大于1的正整数都能被唯一分解为有限个素数的乘积，可写作：

	<math>N = \prod_{i=1}^n p_i^{~~a_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>

2022年2月21日 (一) 11:52 Rmolives

2022-02-21T11:52:09Z

←上一版本		2022年2月21日 (一) 19:52的版本
第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^{a_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>

算数基本定理 - 版本历史

Rmolives：​/* 实现 */

2022年2月22日 (二) 08:56 Rmolives

Rmolives：​/* 实现 */

2022年2月22日 (二) 08:03 Rmolives

2022年2月22日 (二) 08:02 Rmolives

Rmolives：​/* 实现 */

2022年2月22日 (二) 08:00 Rmolives

2022年2月22日 (二) 07:59 Rmolives

2022年2月21日 (一) 11:52 Rmolives

2022年2月21日 (一) 11:52 Rmolives

Rmolives：/* 实现 */

Rmolives：/* 实现 */

Rmolives：/* 实现 */