C 最大公约数 最小公倍数

最小公倍数

int LCW(int m, int n)
{
    int i = m > n ? m : n;
    while (i % m != 0 || i % n != 0)
        i++;
    return i;
}

int fun(int a, int b)
{
    int i, j, m, n;
    if (a > b)
    {
        m = a;
        a = b;
        b = m;
    };
    i = a;
    j = b;
    while ((n = j % i) != 0)
    {
        j = i;
        i = n;
    }
    return i;
};

#include<stdio.h>

int main()
{
    int a = 2, b = 9;
    int lcw = LCW(a, b);
    printf("最小公倍数：LCW:  %d", lcw);
    printf("最大公约数：GCD： %d", a * b / lcw);
    return 0;
}

最大公约数

a * b / lcw 可以用两数的乘积 / 最小公倍数得出

int gcd(int m, int n)
{
    if (m < n)
    {
        int temp = n;
        m = n;
        n = temp;
    }
    if (n == 0)
        return m;
    return gcd(n, m % n);
}

int fun(int a, int b)
{
    int i, j, m, n;
    if (a > b)
    {
        m = a;
        a = b;
        b = m;
    };
    i = a;
    j = b;
    while ((n = j % i) != 0)
    {
        j = i;
        i = n;
    }
    return i;
};

求最大公约数要用到 大数%小数 然后递归 小数 % (大数%小数) 最小为1