[C]最大公约数和最小公倍数

 

/*
求最大公约数和最小公倍数
编写程序，在主函数中输入两个正整数 a,b，调用两个函数 fun1() 和 fun2()，分别求 a 和 b 的最大公约数和最小公倍数，在主函数中输出结果。
*/

#include <stdio.h>
int fun1(int a,int b);
int fun2(int a,int b);
int main()
{
    int a = 0, b = 0, gcd = 0, lcm=0;
    scanf("%d,%d", &a, &b);
    gcd = fun1(a, b);
    lcm = fun2(a, b);
    printf("最大公约数：%d\n", gcd);
    printf("最小公倍数：%d\n", lcm);
    system("pause");
    return 0;

}

//最大公约数 = 小数 与 （大数%小数） 的最大公约数
//若a<b,经过一次辗转相除后，a,b的值会互换，所以不需要考虑a,b谁大

int fun1(int a,int b)
{
    int gcd = 0,r = 0;while (b != 0)//辗转相除法
    {
        r = a % b;
        a = b;
        b = r;
    }
    gcd = a;
    return gcd;

}
//最小公倍数 = 两数相乘 / 最大公约数

int fun2(int a,int b)
{
    int lcm = 0,gcd=0;
    gcd = fun1(a, b);
    lcm = a * b / gcd;
    return lcm;

}

 求最大公约数也可以用递归实现

int f( int m, int n)
 {
     if(m%n==0)
         return n;
     else
         return f(n, m%n);
 }