辗转相除法什么意思

辗转相除法 辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至300年前。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。
证明：
设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq......r 1(0≤r)。若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q......r2 (0≤r2).若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。
[编辑] 算法
辗转相除法是利用以下性质来确定两个正整数 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 b<>0
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;
}
pascal代码（递归）
求两数的最大公约数
function gcd(a,b:integer):in