輾轉相除法
维库，知识与思想的自由文库
輾轉相除法, 又名歐幾里德算法（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 為輸入數值的位數。
