C语言实战：用函数求解最大公约数与最小公倍数的完整指南

1次阅读

没有评论

共计 1476 个字符，预计需要花费 4 分钟才能阅读完成。

最大公约数 (GCD) 和最小公倍数 (LCM) 是数学中的基本概念。GCD 指的是两个或多个整数共有约数中最大的一个，而 LCM 则是能够被这两个数整除的最小正整数。这两个概念在分数运算、密码学等领域有广泛应用。

计算 GCD 主要有两种方法：

暴力枚举法：从较小的数开始递减，找到第一个能同时整除两个数的数。这种方法简单但效率低，时间复杂度为 O(n)。
欧几里得算法：基于 ” 两个数的最大公约数等于其中较小的数和两数相除余数的最大公约数 ” 这一原理，时间复杂度为 O(log n)。

显然，欧几里得算法更为高效，特别是在处理大数时。

欧几里得算法的基本步骤如下：

用较大数除以较小数，得到余数
若余数为 0，则当前较小数即为 GCD
若余数不为 0，则将较小数作为新的较大数，余数作为新的较小数，重复步骤 1

int gcd_recursive(int a, int b) {if (b == 0) return a;
    return gcd_recursive(b, a % b);
}

int gcd_iterative(int a, int b) {
    int temp;
    while (b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

利用数学关系：LCM(a,b) = |a*b| / GCD(a,b)

int lcm(int a, int b) {return abs(a * b) / gcd_iterative(a, b);
}

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

// 函数声明
int gcd_iterative(int a, int b);
int lcm(int a, int b);

int main() {
    int n, m;

    // 输入验证
    do {printf("请输入两个非零整数(空格分隔):");
        scanf("%d %d", &n, &m);
    } while (n == 0 || m == 0);

    // 计算并输出结果
    printf("最大公约数: %d\n", gcd_iterative(n, m));
    printf("最小公倍数: %d\n", lcm(n, m));

    return 0;
}

// 迭代法实现 GCD
int gcd_iterative(int a, int b) {
    // 处理负数
    a = abs(a);
    b = abs(b);

    int temp;
    while (b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算 LCM
int lcm(int a, int b) {
    // 避免整数溢出
    if (a == 0 || b == 0) return 0;

    // 使用绝对值计算
    int gcd = gcd_iterative(a, b);
    return abs(a / gcd * b);
}