如何用函数高效求解最大公约数与最小公倍数：从算法原理到C语言实现

1次阅读

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

在编程和数学计算中，求解两个整数的最大公约数（GCD）和最小公倍数（LCM）是常见需求。无论是在密码学中的密钥生成，还是在图形学中的像素处理，GCD 和 LCM 的计算都扮演着重要角色。本文将从算法原理出发，详细介绍如何用 C 语言高效实现这两个功能。

GCD 的计算有几种常见方法，最基础的是暴力枚举法，即从较小的数开始递减，直到找到一个能同时整除两个数的数。这种方法的时间复杂度为 O(n)，效率较低。

相比之下，欧几里得算法（又称辗转相除法）更为高效，其时间复杂度为 O(log n)。它的基本原理是：GCD(a, b) = GCD(b, a % b)，直到 b 为 0 时，a 即为所求的 GCD。

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) {while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

利用 GCD 可以高效计算 LCM，公式为：

$$ LCM(a, b) = \frac{|a \times b|}{GCD(a, b)} $$

C 语言实现：

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

以下是一个完整的 C 语言程序，包含输入处理和边界条件检查：

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

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

int lcm(int a, int b) {if (a == 0 || b == 0) {return 0;}
    return abs(a * b) / gcd_iterative(a, b);
}

int main() {
    int n, m;
    printf("请输入两个非零整数：");
    scanf("%d %d", &n, &m);

    if (n == 0 || m == 0) {printf("输入不能为零 \n");
        return 1;
    }

    printf("最大公约数：%d\n", gcd_iterative(n, m));
    printf("最小公倍数：%d\n", lcm(n, m));

    return 0;
}

欧几里得算法中的取模运算可以替换为位运算，进一步提高效率：

int gcd_bitwise(int a, int b) {a = abs(a);
    b = abs(b);

    if (a == 0) return b;
    if (b == 0) return a;

    int shift;
    for (shift = 0; ((a | b) & 1) == 0; ++shift) {
        a >>= 1;
        b >>= 1;
    }

    while ((a & 1) == 0) {a >>= 1;}

    do {while ((b & 1) == 0) {b >>= 1;}
        if (a > b) {
            int temp = b;
            b = a;
            a = temp;
        }
        b -= a;
    } while (b != 0);

    return a << shift;
}

在多线程环境下，确保 GCD 函数是线程安全的，避免共享变量。

最佳实践	常见错误
使用迭代实现避免栈溢出	递归实现可能导致栈溢出
处理负数输入	忽略负数输入导致错误结果
添加除零检查	未处理除零情况导致程序崩溃
使用位运算优化性能	未优化导致性能瓶颈