c语言编程 3、 编写程序求出两个正整数的最大公约数与最小公倍数。其中最大公约数是能够整除这两个整

Question

c语言编程
3、 编写程序求出两个正整数的最大公约数与最小公倍数。其中最大公约数是能够整除这两个整数的最大数；最小公倍数是有这两个数的乘积除以最大公约数得出。请分别采用穷举法、欧几里得算法、递归算法求出两个数的最大公约数。其中求最大公约数与最小公倍数分别用两个函数实现。

Answer 1

#include <stdio.h>
#include <stdlib.h>

int exhaustion(int a, int b)    //采用穷举法计算最大公约数
{
    int t = a;
    if(b<a)
        t = b;
    for(; t>0; t--)
    {
        if(a%t==0 && b%t==0)
            break;
    }
    return t;
}

int Euclid(int a, int b)    //采用欧几里得算法求最大公约数
{
    int t;
    while(b!=0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int rec_gcd(int a, int b)   //采用递归算法求最大公约数
{
    return b==0 ? a : rec_gcd(b, a%b);
}

int lcm_fun(int a, int b, int gcd)   //求两个数的最小公倍数
{
    int t = a * b / gcd;
    return t;
}

int main()
{
    int x, y;
    int gcd, lcm;

    printf("请输入两个数并回车，中间以空格隔开：\n");
    scanf("%d %d", &x, &y);

    gcd = exhaustion(x, y);
    printf("采用穷举法计算的最大公约数为：%d\n", gcd);

    gcd = Euclid(x, y);
    printf("采用欧几里德算法计算的最大公约数为：%d\n", gcd);

    gcd = rec_gcd(x, y);
    printf("采用递归算法计算的最大公约数为：%d\n", gcd);

    lcm = lcm_fun(x, y, gcd);
    printf("两数的最小公倍数为：%d\n", lcm);
    return 0;
}