若正整数 #{{a}}# 除以正整数 #{{b}}# 可以整除,则称 #{{b}}# 为 #{{a}}# 的因数(Factor),#{{a}}# 为 #{{b}}# 的倍数(Multiple),#{{1}}# 是所有正整数最小的因数,任意正整数最大的因数就是该正整数本身。若 #{{a}}# 同时是 #{{x}}# 和 #{{y}}# 的因数,则称 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的公因数(Common Divisor),如果 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的公因数中最大的一个,则称 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的最大公因数(Greatest Common Divisor,简称 GCD)。若 #{{a}}# 同时是 #{{x}}# 和 #{{y}}# 的倍数,则称 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的公倍数(Common Multiple);如果 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的公倍数中最小的一个,则称 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的最小公倍数(Least Common Multiple,简称 LCM)。

质因数与质因数分解

若因数是质数(Prime),则称其为质因数(Prime Factor)。找出一个正整数的所有质因数之行为,就称为「质因数分解」(Prime Factorization)。若要对数值不大的正整数 #{{N}}# 做质因数分解,可以利用试除法(Trial Division),找出 #{{2}}# 到 #{{\sqrt{N}}}# 之间的质数,来一个一个测试 #{{N}}# 是否能够被这个范围的质数整除。如果找不到,那 #{{N}}# 的质因数就是 #{{N}}# 的自身。

有关于质数的说明,可以参考这篇文章:

程序如下:

最大公因数

要求两正整数 #{{a}}#、#{{b}}# 的最大公因数,可以利用上面介绍的方式找出两数的所有质因数,再把所有共同的质因数相乘,积就是最大公因数了(短除法的应用)……不过这样做其实挺慢的,以下介绍用辗转相除法求最大公因数的方式,会快很多。

辗转相除法又称欧几里得算法(Euclidean algorithm),相信这个大家在中学阶段都用得吓吓叫了,这边就不再多提。简而言之,要用辗转相除法取得两正整数的最大公因数,那就是把这两数以大除小相除,取余数后,把余数当作原本除数的除数,再进行一次除法。取余数后,再把这个余数当作除数,去除前一个余数,如此反复,直到余数为 0 时,前一个除数就是最大公因数。

程序实作如下:

以上程序,a 为被除数;b 为除数;m 为余数。一开始如果 b 大于 a,会先进行调换。采用辗转相除法的 gcd 函数的时间复杂度为 #{{O((\log a)(\log b))}}#。

对于不擅长处理除法的 CPU,可以改用斯泰因算法(Stein's algorithm),又称为二元 GCD 算法(Binary GCD algorithm)。这个算法是根据以下四个事实来求最大公因数的:

  1. 若 #{{a}}# 和 #{{b}}# 是正偶数,则 #{{gcd(a, b) = 2 \times gcd({a \over 2}, {b \over 2})}}#。(提取公因数 #{{2}}#,最大公因数是所有共同的质因数相乘)
  2. 若 #{{a}}# 是正偶数,#{{b}}# 是正奇数,则 #{{gcd(a, b) = gcd({a \over 2}, b)}}#。(移除 #{{a}}# 的质因数 #{{2}}#,因为 #{{2}}# 不是公因数)
  3. 若 #{{a}}# 和 #{{b}}# 都是正奇数,且 #{{a \gt b}}#,则 #{{gcd(a, b) = gcd(a - b, b)}}#。(若我们要以减法来模拟除法,会用大数去减小数,得到差之后再去减小数,如此循环,看需要减几次才会使得差小于 #{{b}}#,所以 #{{a - b}}# 就是计算 #{{a \over b}}# 的第一步。根据辗转相除法,我们关心的只有 #{{a \over b}}# 的余数和除数,而 #{{a \over b}}# 和 #{{ {a - b} \over b }}#,虽然商数差了 1,但除数和余数是相等的,所以可以如此替换)又因为奇数减奇数必为偶数,根据第 2 个事实,#{{gcd(a - b, b) = gcd({ {a - b} \over 2}, b)}}#。
  4. 若正整数 #{{a}}#、#{{b}}# 相等,则 #{{gcd(a, b) = a}}#。

如此一来,就能将原先的辗转相除法,变成 AND(判断奇偶)、减法、乘以 2 和除以 2 的运算。而对电脑来说,除以 2 或乘以 2 只要去右位移或是左位移一个比特就行了,所以并不需要去计算乘法和除法。根据以上列出的事实外,再另外定义:

  1. #{{gcd(a, 0) = a}}#。(根据辗转相除法,被当作除数的余数为 0 了,就拿上一个余数,也就是现在的被除数作为最大公因数。这只是为了方便递归算法动作,不然 0 是不能求因数的。)
  2. #{{gcd(0, 0) = 0}}#。(这只是为了方便递归算法动作,不然 0 是不能求因数的。)

可以写出以下的 gcd 递归函数:

以迭代的方式来实作二元 gcd 函数:

二元 GCD 算法的时间复杂度为 #{{O((log_{(2)}(a b))^2)}}#。

最小公倍数

要求两正整数 #{{a}}#、#{{b}}# 的最小公倍数,只要将它们相乘,再除以它们的最大公因数就好了。