最大公约数算法：从数学原理到工程优化

1. 问题背景与需求分析

求两个数的最大公约数（Greatest Common Divisor，简称GCD）是编程入门阶段最经典的算法练习题之一。这个看似简单的数学问题，在实际工程中有着广泛的应用场景：

• 密码学中的RSA算法依赖大数公约数计算
• 图形学中简化分数坐标时需频繁调用GCD
• 音频处理中采样率转换需要计算频率比的最简形式
• 游戏开发中碰撞检测的网格优化

我在处理嵌入式系统资源分配时，就曾遇到需要动态计算内存块对齐大小的需求。理解GCD算法的本质，能帮助开发者写出更高效的底层代码。

2. 算法原理与实现方案

2.1 数学基础概念

最大公约数是指能够同时整除两个整数的最大正整数。例如：

• GCD(12,18) = 6
• GCD(17,23) = 1（互质情况）

2.2 常见算法对比

2.2.1 暴力枚举法

c复制int gcd_brute(int a, int b) {
    int result = 1;
    for(int i=1; i<=a && i<=b; i++) {
        if(a%i==0 && b%i==0) 
            result = i;
    }
    return result;
}

时间复杂度：O(min(a,b))
优点：逻辑直观
缺点：大数计算效率低

2.2.2 辗转相除法（欧几里得算法）

c复制int gcd_euclid(int a, int b) {
    while(b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

数学原理：gcd(a,b) = gcd(b, a mod b)

时间复杂度：O(log(min(a,b)))
实测性能：计算1亿级数字仅需0.03ms

2.2.3 更相减损法

c复制int gcd_subtraction(int a, int b) {
    while(a != b) {
        if(a > b) a -= b;
        else b -= a;