在 Kotlin 中计算最大公约数

1. 简介

计算两个数的最大公约数（GCD）是数论中的基础操作，在计算机科学和数学中有着广泛的应用。

本文将介绍如何在 Kotlin 中实现 GCD 的计算算法。

2. 最大公约数（GCD）概念

✅ 最大公约数是指能同时整除两个正整数的最大正整数。它也被称为最高公因数（HCF）或最大公因子（GCF）。
⚠️ 注意：任意两个正整数的 GCD 至少为 1，因此 GCD 永远不会是负数或零。

计算两个正整数 a 和 b 的 GCD 公式如下：

GCD(a, b) = a × b / LCM(a, b)

其中，最小公倍数（LCM）是指能被所有给定数字整除的最小正整数。使用该公式时，我们先计算两数乘积，再求出它们的 LCM，最后用乘积除以 LCM 得到 GCD。

💡 虽然这个公式成立，但在实际编程中并不常用，因为求 LCM 本身也需要 GCD，容易陷入循环依赖。更高效的方式是直接使用欧几里得算法。

3. 计算两个数的 GCD

有多种算法可用于计算 GCD，其中最经典且高效的是欧几里得算法（Euclidean Algorithm），它专门用于求解两个整数的最大公约数。

3.1. 欧几里得算法原理

核心公式如下：

GCD(a, b) = GCD(b, a mod b)

我们以 a = 48、b = 18 为例演示计算过程：

GCD(48, 18) → GCD(18, 48 % 18 = 12)
GCD(18, 12) → GCD(12, 18 % 12 = 6)
GCD(12, 6) → GCD(6, 12 % 6 = 0)
当余数为 0 时停止，此时最后一个非零余数就是 GCD → 结果为 6

整个过程通过不断取模并交换数值，直到余数为零为止。

3.2. 代码实现

fun calculateGCD(a: Int, b: Int): Int {
    var num1 = a
    var num2 = b
    while (num2 != 0) {
        val temp = num2
        num2 = num1 % num2
        num1 = temp
    }
    return num1
}

📌 实现说明：

使用 while 循环持续执行欧几里得算法，直到 num2 == 0
每轮迭代更新 num1 和 num2，其中 num2 始终接收上一轮的余数
✅ 最终 num1 即为所求 GCD

⚠️ 小贴士：初始传参顺序不影响结果。算法内部通过交换机制自动处理大小关系，无需手动保证 a > b。

单元测试验证

@Test
fun `Should calculate GCD for two integers`() {
    assertEquals(6, calculateGCD(18, 48))
    assertEquals(1, calculateGCD(17, 5))
    assertEquals(9, calculateGCD(27, 18))
    assertEquals(15, calculateGCD(75, 45))
}

这些测试覆盖了常见场景，包括互质数（如 17 和 5）、典型合数等，确保算法鲁棒性。

4. 计算多个数的 GCD

实际开发中，有时需要求一组数的公共最大公约数。我们可以利用 GCD 的结合律性质：
👉 GCD(a, b, c) = GCD(GCD(a, b), c)

基于此，逐个合并即可。

实现代码

fun calculateGCDForListOfNumbers(numbers: List<Int>): Int {
    require(numbers.isNotEmpty()) { "List must not be empty" }
    var result = numbers[0]
    for (i in 1 until numbers.size) {
        var num1 = result
        var num2 = numbers[i]
        while (num2 != 0) {
            val temp = num2
            num2 = num1 % num2
            num1 = temp
        }
        result = num1
    }
    return result
}

📌 关键点解析：

❌ 输入为空列表时直接抛出 IllegalArgumentException，避免后续空指针风险
从第一个数开始，依次与后续每个数计算 GCD，逐步收敛最终结果
内层仍使用欧几里得算法处理每一对数值

测试用例

@Test
fun `Should calculate GCD for list of two Integers`() {
    val result = calculateGCDForListOfNumbers(listOf(21, 36))
    assertEquals(3, result)
}

@Test
fun `Should calculate GCD with three Integers`() {
    val result = calculateGCDForListOfNumbers(listOf(10, 20, 30))
    assertEquals(10, result)
}

✅ 验证成功：[10,20,30] 的 GCD 是 10，符合预期。

边界情况测试

@Test
fun `Should fail on empty list`() {
    assertFailsWith<IllegalArgumentException> {
        calculateGCDForListOfNumbers(emptyList())
    }
}

⚠️ 踩坑提醒：集合类算法最容易忽略边界条件。生产代码中务必对空输入做防御性检查，否则线上可能触发 IndexOutOfBoundsException。

5. 总结

本文介绍了最大公约数（GCD）的基本概念，并通过 Kotlin 实现了基于欧几里得算法的 GCD 计算方案：

✅ 掌握了 GCD 的数学定义及其递推公式
✅ 实现了高效的双数 GCD 计算函数
✅ 扩展支持了列表形式的多数值 GCD 计算
✅ 添加了必要的异常处理与单元测试保障可靠性

所有示例代码均已开源，可在 GitHub 获取完整项目：

👉 https://github.com/Baeldung/kotlin-tutorials/tree/master/core-kotlin-modules/core-kotlin-9

Persistence

REST

Security