高校问答万网添加多个二级域名:看看c语言的这个 算法为什么
来源：百度文库 编辑：高校问答 时间：2024/05/01 09:34:48
求两个数（x>y）的最大公因子：
for(r=x%y;r;r=x%y)
{
x=y;y=r;
}
printf(最大公因子:%d",y);
为什么辗转求余后就可以求出来?
for(r=x%y;r;r=x%y)
{
x=y;y=r;
}
printf(最大公因子:%d",y);
为什么辗转求余后就可以求出来?
是个数学问题~
比如 我们令 x=60 y=25 （很明显最大公因子为5）
而算法的步骤是
60/25=2......10
如果 25能整除余数10 那么60就能整除25了 但这显然不行 所以继续
25/10=2......5 同上 继续
10/5=2......0 行了能整除了 我们从下往上推
就知道了 5能被60 25 整除，且是最大的~~~~~~~~
（当然 当x本就是y的一个因子时，一步就完了~）
这牵涉到辗转相除法的原理了。
辗转相除法的算理是根据：在a=bq+r，中，除数b和余数r能被同一个数整除，那么被除数a也能被这个数整除。或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数；如果反过来说，被除数与除数的最大公约数，就是除数与余数的最大公约数
如果用辗转相除法求两个数的最大公约数时，最后的余数是1，那么这两个数就是互质数，或者说，它们只有公约数1。
这是数学问题，不是 C 语言问题，而且，这是阿基米德发明的算法，你可以问他老人家。
你去买一本《计算机程序设计艺术（英文影印版》，清华大学出版社，Donald e.knuth
第三版，第一卷
你问的问题答案在第5页
哈哈，同意楼上的，虽然搞了这么久，还没头一回真正知道其含义，
数学问题.就是计算机的根本