Question

求最大公约数最快方法

Answer 1

求最大公约数最快方法如下：

求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。

1、个合数都可以写成几个质数相乘的形式，这几个质数就都叫作这个合数的质因数如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数。

而这个因数一定是一个质数，质因数就是一个数的约数并且是质数比如8=2乘2乘2，2就是8的质因数，12＝2×2×3，2和3就是12的质因数把一个式子以12＝2×2×3的形式表示，叫作分解质因数。

2、短除法是算术中除法的算法将除法转换成一连串的运算，短除法是由长除法简化而来当中会用到心算，因此除数较小的除法比较适用短除法，对大部分的人而言若除以12或12以下的数可以用记忆中乘法表的内容用心算来进行短除法。

也有些人可以处理除数更大的短除法，在短除法中要将一个数（称为被除数）除以除数所得的结果称为商数。

3、辗转相除法又名欧几里德算法是求两个正整数值最大公约数的算法，它是已知最古老的算法其可追溯至公元前300年前。

它的具体做法是用较大数除以较小数，再用出现的余数（第一余数）去除除数再用出现的余数（第二余数）去除第一余数，如此反复直到最后余数是0为止。