若正整數#{{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}}#到#{{N}}#之間的質數,來一個一個測試#{{N}}#是否能夠被這個範圍的質數整除。

有關於質數的說明,可以參考這篇文章:

https://magiclen.org/prime-number/

程式如下:

最大公因數

要求兩正整數#{{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)}}#。(若我們要以減法來模擬除法,會用大數去減小數,得到差之後再去減小數,如此循環,看需要減幾次才會使得差小於等於0,所以#{{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}}#的最小公倍數,只要將它們相乘,再除以它們的最大公因數就好了。