计算机代码如下:
function gcd(a, b) {
if a mod b<>0
return gcd(b, a mod b);
else
return b;
}
或纯使用循环:
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 为输入数值的位数。