笔记大全

c语言怎么求最大公约数和最小公倍数

更新时间：2023-10-28

最大公约数

求两个数的最大公约数，需要用到辗转相除法。辗转相除法的原理是，对于整数a、b，设r是a÷b的余数，若r=0，则b是a的最大公约数。否则，令a=b，b=r,再计算a÷b的余数，重复此步骤，直到余数为0为止。以下是C语言实现代码：

#include 

// 求最大公约数
int gcd(int a, int b)
{
    int r;
    while(b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    int a, b, result;
    printf("请输入两个整数，用空格隔开：");
    scanf("%d %d", &a, &b);
    result = gcd(a, b);
    printf("%d 和 %d 的最大公约数为：%d", a, b, result);
    return 0;
}

最小公倍数

求两个数的最小公倍数，需要用到它们的最大公约数。最小公倍数等于两数之积除以它们的最大公约数。以下是C语言实现代码：

#include 

// 求最大公约数
int gcd(int a, int b)
{
    int r;
    while(b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 求最小公倍数
int lcm(int a, int b)
{
    int result = a * b / gcd(a, b);
    return result;
}

int main()
{
    int a, b, result;
    printf("请输入两个整数，用空格隔开：");
    scanf("%d %d", &a, &b);
    result = lcm(a, b);
    printf("%d 和 %d 的最小公倍数为：%d", a, b, result);
    return 0;
}

异常处理

当输入的数据不是正整数时，辗转相除法和最小公倍数的计算结果可能有误。为了避免这种情况的发生，我们需要在程序中加入异常处理机制。以下是C语言实现代码：

#include 

// 求最大公约数
int gcd(int a, int b)
{
    int r;
    while(b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 求最小公倍数
int lcm(int a, int b)
{
    int result = a * b / gcd(a, b);
    return result;
}

int main()
{
    int a, b, result, isValid = 1;
    printf("请输入两个正整数，用空格隔开：");
    if(scanf("%d %d", &a, &b) != 2 || a <= 0 || b <= 0)
    {
        isValid = 0;
    }

    if(isValid)
    {
        result = lcm(a, b);
        printf("%d 和 %d 的最小公倍数为：%d", a, b, result);
    }
    else
    {
        printf("输入有误，两个数必须为正整数");
    }
    return 0;
}

总结

C语言求最大公约数和最小公倍数的算法都是基于辗转相除法。辗转相除法的原理是，对于整数a、b，设r是a÷b的余数，若r=0，则b是a的最大公约数。否则，令a=b，b=r,再计算a÷b的余数，重复此步骤，直到余数为0为止。最小公倍数等于两数之积除以它们的最大公约数。

辗转相除法和最小公倍数的计算需要输入两个正整数，并且需要进行异常处理，当输入的数据不是正整数时，程序会输出错误信息。

以上是C语言求最大公约数和最小公倍数的代码实现，希望对大家有所帮助。

c语言编程笔录