2024-11-19 厉飞雨 阅读(2) 评论(0) 赞(0)

很早就学过欧几里得算法，但是一直不知道它的原理。几乎每本算法书都会提到它，但是貌似只有数学书上才会见到它的原理。。。 前段时间粗粗看了点数论（《什么是数学》），惊讶于这个原理的奇妙。现在把它通俗地写下来，以免自己忘记。 欧几里得算法是求两个数的最大公约数(Greatest Common Divisor (GCD))的算法，我们首先假设**有两个数 $a$ 和 $b$，其中 ...