使用连续整数检测与分解质因数法求最大公约数

本文主要介绍了三种不同的方法来计算两个整数的最大公约数（Greatest Common Divisor, GCD）：欧几里得算法、最小公倍数法以及分解质因数法。 1. 欧几里得算法： 欧几里得算法是最古老的算法之一，用于寻找两个正整数的最大公约数。它基于以下原理：两个正整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。这个过程不断重复，直到余数为零，此时较小的数就是最大公约数。在给定的代码中，`CommonFactor` 函数通过一个`while`循环实现了这一过程。首先计算 m % n 的余数 r，然后交换 m 和 n 的值，将 r 赋给 n，再继续执行循环，直至 r 为零。 2. 最小公倍数法： 另一种方法是通过找到两个数的最小公倍数（Least Common Multiple, LCM），然后用两数之积除以 LCM 来得到 GCD。在提供的代码中，`gcd` 函数使用了这种方法。首先找到 m 和 n 中的较小值 t，然后遍历从 t 到 1，检查每个数是否同时能整除 m 和 n。当找到这样的数时，返回该数作为 GCD。 3. 分解质因数法： 分解质因数法是将两个数分别分解成质因数的乘积，然后找出共同的质因数并相乘得到 GCD。在 `decompose` 函数中，输入的数 num 被分解成质因数，并存储在数组 a[] 中。`CommonFactor` 函数比较两个数组 a[] 和 b[]，找出它们共有的质因数，并将其相乘得到 GCD。这个方法更适用于理解两个数的因数结构，但可能在处理大数时效率较低。 以上三种方法都可以有效求解最大公约数，但效率和适用场景各有不同。欧几里得算法简单且高效，适用于大多数情况；最小公倍数法在某些特定情况下可能更快；而分解质因数法则在需要分析因数结构时更为合适。在实际编程中，通常会选择欧几里得算法或其优化版本（如辗转相除法）来求解最大公约数，因为它具有较高的计算效率。