辗转相除法

Sapphire

2022/2/13

解题思路:

寻找两个数之间的最大公约数，我们所用的方法为辗转相除法(迭代)，又称欧几里得算法，具体做法是用较大数除以较小数，再用出现的余数去除以除数，如此反复，直到最后的余数为0为止。

即(m,n)=(n,r)=(r,x)，m和n的最大公约数等于n和r的最大公约数也等于r和x的最大公约数，其中r=m%n，x=n%r。意思就是说被除数与除数的最大公约数即是除数与余数的最大公约数，如此迭代下去。

以上算法我们用此语句实现:

int r;
while(m%n)
{
    r=m%n;
    m=n;
    n=r;
}
return n;

比如我们输入数字:

1. m=24，n=18，while(24%18)即while(6)于是执行代码块中语句，r=6，m=18，n=6，下一次时while(m%n)即while(0)，所以return 6，6就是两个数字的最大公约数。//(24,18)=(18,6)，所以最大公约数为6

2. m=18，n=24，while(18%24)即while(18)于是执行代码块中语句，r=18，m=24，n=18，也可以把较大数字赋值成为m，较小数字赋值成n。//(18,24)=(24,18)=(18,6)，所以最大公约数为6

注意事项:

1. 最小公倍数=两数的乘积/最大公约数

参考代码:

#include<stdio.h>
int GCD(int m,int n)//最大公约数
{
    int r;
    while(m%n)
    {
        r=m%n;
        m=n;
        n=r;
    }
    return n;
}
int LCM(int m,int n)//最小公倍数
{
    return m*n/GCD(m,n);
}
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    printf("%d\n",GCD(m,n));
    printf("%d",LCM(m,n));
    return 0;
}