❶ C語言問題
輾轉相除法
輾轉相除法, 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。它是已知最古老的演算法, 其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。
輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余數, 則
gcd(a,b) = gcd(b,r)
2. a 和其倍數之最大公因子為 a。
另一種寫法是：
1. a ÷ b，令r為所得余數（0≤r＜b）
若 r = 0，演算法結束；b 即為答案。
2. 互換：置 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 為輸入數值的位數。