Question

欧几里得算法（辗转相除法）

这个算法就是求最大公约数，但网上资料都是证明这条定理，不知如何求最大公约数，只记得两条竖线，望帮助

Answer 1

就是把上一轮有余数的除法计算中，
除数变为下一轮计算的被除数，
余数变为下一轮计算的除数，
一直这样计算下去，
直到最后一次计算余数为零，
在最后一轮计算中的被除数，即为所求的最大公约数。
举例：
105和85的最大公约数
第一轮计算
105÷85=1...20
第二轮计算
85÷20=4...5
第三轮计算
20÷5=4
第三轮没有余数，
因此
105和85的最大公约数就是第三轮计算的被除数
5.
至于C语言编程，下边是我自己写的G函数(思想就是辗转相除法求最大公约数)
int
G(int
x,int
y)
{
int
t;
while(y!=0)
{
t=x%y
;
x=y;
y=t;
}
return
x;
}