辗转相除的代码

计算机代码如下：

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）。

C程序： int m,nscanf(%d%d,&m,&n)int a = m,b = n//8 12//8 % 12  8//12 % 8  4//8 % 4   0//12 8//12 % 8  4//8 % 4   0while (m % n != 0) {int temp = m % nm = nn = temp}printf(%d %d\n,n,a * b / n)辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。

辗转相除法的算法步骤为，两个数中用较大数除以较小数，再用出现的余数（第一余数）去除除数。

再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。得到最后的除数就是这两个数的最大公约数。

扩展资料：

扩展欧几里得算法可用于RSA加密等领域。

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公约数为1