最大公约数和最小公倍数

文章时效性提示

本文发布于 499 天前，部分信息可能已经改变，请注意甄别。

题目：输入两个正整数m和n，求其最大公约数和最小公倍数。

最大公约数（Greatest Common Divisor, GCD）是指两个或多个整数共有约数中最大的一个。例如，12和30的公约数有1、2、3、6，其中6就是12和30的最大公约数‌。

（1）最小公倍数=两个数的积/最大公约数
（2）求最大公约数用辗转相除法（又名欧几里德算法）

思路：通过两个函数分别计算这两个数字的最大公约数和最小公倍数。

---

int GCD(int m,int n)//求最大公约数
{
    if (n>m)//始终让m里面的数字是大的
    {
        int temp;
        temp = n;
        n = m;
        m = temp;
    }
    //开始辗转相除
    int remainder = m % n;//余数
    while (remainder) {
        m = n;
        n = remainder;
        remainder = m % n;
    }
    return n;
}

int LCM(int gcd,int m,int n)
{
    return (m*n/gcd);
}
  
int main() {
    int m,n;
    printf("请输入两个正整数m和n，求其最大公约数和最小公倍数:->");
    scanf("%d,%d",&m,&n);
    int gcd = GCD(m,n);
    int lcm = LCM(gcd,m,n);
    printf("最大公约数是:%d\n",gcd);
    printf("最小公倍数是:%d",lcm);
    return 0;
}