輾轉相除法
维基百科,自由的百科全书
輾轉相除法, 又名歐幾里德算法(Euclidean algorithm)乃求兩個正整數之最大公因數的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》(第VII卷,命题i和ii)中,而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因數分解。
[编辑] 算法
輾轉相除法是利用以下性質來確定两个正整数 a 和 b 的最大公因數的:
- 若 r 是 a ÷ b 的餘數, 則
- gcd(a,b) = gcd(b,r)
- a 和其倍數之最大公因數為 a。
另一種寫法是:
- a ÷ b,令r为所得余数(0≤r<b)
- 若 r = 0,算法结束;b 即为答案。
- 互换:置 a←b,b←r,并返回第一步。
[编辑] 虛擬碼
這個算法可以用递归寫成如下:
function gcd(a, b) { if (a 不整除 b) return gcd(b, a mod b); else return a; }
或純使用迴圈:
function gcd(a, b) { define r as integer; while b ≠ 0 { r := a mod b; a := b; b := r; } return a; }
其中“a mod b”是指取 a ÷ b 的餘數。
例如,123456 和 7890 的最大公因數是 6, 這可由下列步驟看出:
a | b | a mod b |
123456 | 7890 | 5106 |
7890 | 5106 | 2784 |
5106 | 2784 | 2322 |
2784 | 2322 | 462 |
2322 | 462 | 12 |
462 | 12 | 6 |
12 | 6 | 0 |
只要可計算餘数都可用輾轉相除法來求最大公因數。這包括多項式、複整數及所有歐幾里德定義域(Euclidean domain)。
輾轉相除法的運算速度為 O(n2),其中 n 為輸入數值的位數。
[编辑] References
Donald Knuth, The Art of Computer Programming, volume 1 and volume 2. Addison-Wesley.