在C语言中用辗转相除法求两个整数值的最大公约数

最大公约数"/>

在C语言中用辗转相除法求两个整数值的最大公约数

1.首先了解一下什么是辗转相除法

 将两个整数值作为长方形的边长。用短边为边长的正方形来填充长方形，对剩余部分持相同操作，直到填满为止，填充过程中最小的正方形边长就是两个整数值的最大公约数。

2.思路

前边提到该方法首先是以最短边为正方形填充，那我们先要分别长短边，判断短边是否为最大公因数，是的话就结束，不是的话就找下一个短边，如上图中寻找长度为2的边，就是上一个长边短边之差，或者相磨。找到以后会有新的长短边，重复开始时的过程，这里用到了递归解决。

3.程序

#include<stdio.h>
int gcd(int x, int y)
{
    int max;
    int min;
    int ret;
    if (x > y)
    {
        max = x; 
        min = y;
    }
    else
    {
        max = y;
        min = x;
    }
    if (max % min == 0)
        return min;
    ret = max % min;
    if (x % ret == 0 && y % ret == 0)
        return ret;
    else
        return gcd(ret, min);
}
int main()
{
    int x;
    int y;
    printf("输入两个数，求最大公因数"); scanf("%d %d", &x, &y);
    printf("%d", gcd(x, y));
    return 0;
}