辗转相除法求最大公约数（递归函数）

递归函数）"/>

辗转相除法求最大公约数（递归函数）

  辗转相除法，又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它的原理是通过不断地用较小的数去除较大的数，直到两个数相等为止（余数为零），这个相等的数就是它们的最大公约数。

  简单来说：1、先用小的一个数除大的一个数，得第一个余数；
                    2、再用第一个余数除小的一个数，得第二个余数；
                    3、又用第二个余数除第一个余数，得第三个余数；
                    4、这样逐次用后一个数去除前一个余数，直到余数是0为止。最后一个除数就是所求的最大公约数。

接下来我们用函数实现：

#include<stdio.h>
int Quto(int x, int y)
{int temp = 0;if (x > y)先判断x和y哪个大 哪个小{temp = x % y;//用大数除以小数得到第一个余数if (temp!= 0)//判断第一个余数是否为零，是的话直接返回y，不是的话返回Quto（）函数，继续计算{return Quto(y, temp);}else{return y;}}else //这里是x<y的情况{temp = y % x;if (temp != 0){return Quto(x, temp);}else{return x;}}}
int main()
{int x = 0;int y = 0;int q = 0;printf("输入你想求最大公约数的两个数\n");while (scanf_s("%d%d", &x, &y) != EOF){int q = Quto(x, y);printf("他们的最大公约数为%d\n", q);getchar();}return 0;
}

这就是用递归方法去求最大公约数，递归不太懂的可以去看我第二篇有关递归知识讲解的博客