0Pricing
Coding Interview Prep · 课时

GCD、LCM 与欧几里得算法

快速且准确地计算因数

GCD、LCM 与欧几里得算法 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

为什么因数很重要

许多竞赛题都与两个数的公因数有关。这里最有用的工具就是GCD，即最大公约数。🔢

GCD 的含义

两个整数的 GCD 是能够同时整除它们且没有余数的最大数。对于 12 和 18，它是 6，因为 6 可以整除这两个数。

缓慢的方法

您可以从较小的数开始向下测试每个数，直到找到一个能同时整除两者的数。这种方法虽然可行，但对于较大的输入来说太慢了。

欧几里得算法的要点

欧几里得算法是一种快速方法。它的核心思想是：a 和 b 的 GCD 等于 b 与 a 除以 b 所得余数的 GCD。

递推过程

不断重复交换和取模的步骤，直到余数变为零。最后剩下的非零值就是您的答案，也就是 GCD 本身。

gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = a

亲自编写代码

一个简短的循环会不断替换这两个数，直到 b 变为零。该方法大约只需 log 步，即使处理极大的数也非常快。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

使用标准库

您很少需要手动实现它。Python 提供了 math.gcd，它正确、快速，还会替您处理零参数。

from math import gcd
print(gcd(12, 18))

从 GCD 到 LCM

LCM 即最小公倍数，是能够同时被两个数整除的最小数。它与刚刚计算出的 GCD 直接相关。

LCM 公式

将两个数相乘，再除以它们的 GCD。对于非常大的乘积，请始终先做除法，以避免溢出。

def lcm(a, b):
    return a // gcd(a, b) * b

整个列表的 GCD

要计算多个数的 GCD，可以逐对连续计算。Python 的归约函数会将 math.gcd 按从左到右的顺序应用于列表。

from functools import reduce
from math import gcd
g = reduce(gcd, nums)

处理零的情况

根据定义，gcd(a, 0) 等于 a，而 gcd(0, 0) 等于 0。了解这个边界情况

快速检查

现在确认一下欧几里得算法的核心步骤。

回顾

现在您可以使用欧几里得算法，在 log 步内计算 GCD，由此推导 LCM，并对列表中的多个数连续计算二者。✅

常见问题解答

「GCD、LCM 与欧几里得算法」课时是免费的吗？

是的 — 「GCD、LCM 与欧几里得算法」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「GCD、LCM 与欧几里得算法」这节课中我会学到什么？

快速且准确地计算因数 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

「GCD、LCM 与欧几里得算法」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. GCD、LCM 与欧几里得算法
  2. 测试截至 sqrt(n) 的素性
  3. 埃拉托斯特尼筛法
  4. 质因数分解与因数
← 返回 Coding Interview Prep