C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

解题思路:

解这题最重要的就是求出最大公约数，然后最小公倍数就好求了

这题有两种解法：辗转相除法和更相减损法，这我在代码的注释中写了这两种方法怎么用

注意事项:

我把两种方法都写在这里，更相减损法比较复杂，感兴趣的可以看一下

红色字体的是辗转相除法，黑色字体的是更相减损法

参考代码:

#include<stdio.h>

int main()         //辗转相除法求最大公约数和最小公倍数

{                  

    int m, n;

    int a;

    int i, j;

    scanf("%d%d", &m, &n);

    i = m;

    j = n;

    while(i%j != 0)//辗转相除法求最大公约数

    {              //就是用大的数字除以小的数字，把这个比较小的数字当做下一次相除中大的值，

                   //把余数当做小值，如此循环，直到余数为0的时候为止，此时被除的数就是最大公约数

        a = i%j;

        i = j;

        j = a; 

    }

    i = m*n / j;   //最小公倍数就等于两个数相乘除以最大公约数

    printf("%d %d", j, i);

    return 0;

}

/*

#include<stdio.h>

int main()             //更相减损法求最大公约数和最小公倍数

{

    int m, n;

    int a, b = 1;

    int i, j;

    scanf("%d%d", &m, &n);

    while(m%2 ==0)     //约简，原因在后面写了

        while(n%2 ==0)

            {

                m=m/2;

                n=n/2;

                b *= 2;

                break;

            }

    i = m;

    j = n;

                           //更相减损法求最大公约数如果两个数都是偶数，要约简

    while(i != j)    //更相减损法就是以较大的数减较小的数，接着把所得的差与较小的数比较，

    {                    //并以大数减小数。继续这个操作，直到所得的减数和差相等为止

        while(i > j) //前面约掉的若干个 2 与这一步中等数的乘积就是所求的最大公约数

        {

            a=i-j;

            i=j;

            j=a;

        }

        while(i < j) //让 i 成为大数，j 成为小数

        {

            a=j;

            j=i;

            i=a;

        }

    }

    j = m*n / i * b;         //前面约简的数在这里要乘上

    printf("%d %d", i*b, j);  //前面约简的数在这里要乘上

    return 0;

}

*/