1、輾轉(zhuǎn)相除法 開放分類： 數(shù)學、最大公約數(shù) 輾轉(zhuǎn)相除法, 又名歐幾里德算法（Euclidean algorithm）乃求兩個正整數(shù)之最大公因子的算法。

【資料圖】

2、它是已知最古老的算法, 其可追溯至前300年。

3、它首次出現(xiàn)于歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現(xiàn)的《九章算術(shù)》。

4、它并不需要把二數(shù)作質(zhì)因子分解。

5、 證明： 設(shè)兩數(shù)為a、b(b＜a)，求它們最大公約數(shù)(a、b)的步驟如下：用b除a，得a＝bq?1＋r?1（0≤r?1＜b）。

6、若r?1=0，則(a，b)＝b；若r?1≠0，則再用r?1除b，得b＝r?1q?2＋r?2（0≤r?2＜r?1）。

7、若r?2＝0，則(a，b)＝r?1，若r?2≠0，則繼續(xù)用r?2除r?1，……如此下去，直到能整除為止。

8、其最后一個非零余數(shù)即為(a，b)。

9、 [編輯] 算法 輾轉(zhuǎn)相除法是利用以下性質(zhì)來確定兩個正整數(shù) a 和 b 的最大公因子的： 1. 若 r 是 a ÷ b 的余數(shù), 則 gcd(a,b) = gcd(b,r) 2. a 和其倍數(shù)之最大公因子為 a。

10、 另一種寫法是： 1. a ÷ b，令r為所得余數(shù)（0≤r＜b） 若 r = 0，算法結(jié)束；b 即為答案。

11、 2. 互換：置 a←b，b←r，并返回第一步。

12、 [編輯] 虛擬碼 這個算法可以用遞歸寫成如下: function gcd(a, b) { if a mod b0 return gcd(b, a mod b); else return a; } 或純使用循環(huán): 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 的余數(shù)。

13、 例如，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 只要可計算余數(shù)都可用輾轉(zhuǎn)相除法來求最大公因子。

14、這包括多項式、復(fù)整數(shù)及所有歐幾里德定義域（Euclidean domain）。

15、 輾轉(zhuǎn)相除法的運算速度為 O(n2)，其中 n 為輸入數(shù)值的位數(shù)。

本文到此分享完畢，希望對大家有所幫助。