两正整数最大公约数怎么求（两个整数的最大公约数和最小公倍数的快速计算方法）

gcd（greatest common divisor）表示最大公约数，lcm（least common multiple）表示最小公倍数，今天小编就来说说关于两正整数最大公约数怎么求?下面更多详细答案一起来看看吧!

两正整数最大公约数怎么求

gcd（greatest common divisor）表示最大公约数，

lcm（least common multiple）表示最小公倍数。

小学教材中求几个数的最大公约数的方法是分解质因数法：先将几个数分别进行分解质因数，然后再把几个数中的全部公有质因数提取出来连乘，所得的积就是最大公约数。

还可以使用短除法：先用这几个数的公约数连续去除，一直除到所有的商互质为止，然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。

无论是短除法，还是分解质因数法，在质因数较大时，都会觉得困难。这时就需要用新的方法——欧几里得算法（也叫辗转相除法）来求。

计算公式：gcd(a, b) = gcd(b, a mod b) （a>b）即a与b（a>b）两数的最大公约数等于b与a除以b所得的余数的最大公约数。

当a mod b 的结果为0时，gcd（b, 0）=b

例如：

gcd(1178, 341) 1178 mod 341=155

=gcd(341, 155) 341 mod 155=31

=gcd(155, 31) 155 mod 31=0

=gcd(31, 0)

=31

因为

所以