如何一步步通过算法实践寻找最大公约数？

本文共计1212个文字，预计阅读时间需要5分钟。

前言：在实现之前，我们先来了解一下什么是最大公约数，以及我们常用的计算最大公约数的方法，或者说是数学方法。

概念：最大公约数，也称最大公因数，是指两个或多个整数共有的最大的约数。它包括最大公约因数、最大公约因数和最大公约因式。

它是：一个能够被若干整数整除的最大的整数。

前言

在实现之前我们先来了解一下什么是最大公约数，以及我们常用的计算最大公约数的方法或者说数学方法。

概念

最大公约数，也称最大公因数、最大公因子。他是一个能够被若干整数同时整除的整数，如果一个整数同时是几个整数的约数，则称这个整数为他们的公约数，公约数中最大的数成为最大公约数，1是任意若干的正整数的公约数。比如：一个数既是数A的约数，又是数B的约数，称为A,B的公约数，A,B的公约数中最大的一个（可以包括AB自身）称为AB的最大公约数，a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。这么一大段可以概括为：

最大公约数：指两个或多个整数共有约数中最大的一个。

求最大公约数的方法

常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。（先埋个小彩蛋：下一篇文章我们可以接着探索一下最小公倍数的计算方法）

短除法和辗转相除法是我们在数学解题中常用的两种方法。而且短除法也是我们在求二进制数时常用的方法，辗转相除法求可用来求解不定方程的一组整数解，这是它在数学中最常见的应用，辗转相除法处理大数时非常高效，它需要的步骤不会超过较小数的位数(十进制下)的五倍（加百利·拉梅(GabrielLamé)于1844年证明了这点，开创了计算复杂性理论）。辗转相除法的运算速度为 O(n)，其中 n 为输入数值的位数。