要求最大公约数是什么含义（要求的含义是什么意思）

原标题：要求最大公约数是什么含义（要求的含义是什么意思）

　　最大公约数

要求最大公约数是什么含义

　　那么，什么是公约数？什么是最大公约数？

　　公约数，顾名思义，就是能被两个数同时整除的一些数。而最大公约数就是这些数中的最大值。

　　含义

　　举个例子，比如我们要求96和50的最大公约数。

要求的含义是什么意思

　　应该怎么做呢？

　　首先，我们要将96和50分别进行质因式分解，也就是将它们写成质数乘积的形式。

　　那何为质数？

　　质数，又叫素数。指只能被自身和1整除的数。

　　那么96=2x2x2x2x2x3, 50=2x5x5

　　然后，找出质因式中二者共同的质数。对比上面两个式子，我们发现二者共同的只有2.

　　因此，96和50的最大公约数就是2.

　　如果两个数相同的质因数多于1个呢？那么最大公约数就是这些质因数的乘积。

　　再来举个例子，我们要求90和50的最大公约数。

　　90=2·3·3·5, 50=2·5·5

　　二者相同的质因数有2和5，因此它们的最大公约数就是2·5=10.

　　上面介绍的是我们传统的方法，好像也没什么问题，操作起来也简单。

　　但这只适用于比较小的数字，如果数字很大，那么用这种方法就会费时又费力。

　　这时，就需要用到一个世界上最古老的算法——欧几里得算法了。

　　欧几里得算法

　　欧几里得算法，就叫辗转相除法。因为最早被发现记录于欧几里得的着作中，因此就以其名字来命名。这个算法就是用来求两个数的最大公约数的。

　　

　　接下来，我们就来看看欧几里得算法的具体步骤。

公约

　　比如我们要求1234和678的最大公约数。

　　首先，我们要计算1234 mod 678，这个mod是取余运算符，这个式子的结果就是1234除以678的余数。

　　即1234 mod 678=556

　　继续计算678 mod 556=122

　　继续556 mod 122=68

　　继续122 mod 68=54

　　继续68 mod 54=14

　　继续54 mod 14=12

　　继续14 mod 12=2

　　继续12 mod 2=0

　　当所得的余数为0时，最后一次运算中的除数就是我们要求的最大公约数。

　　因此，1234和678的最大公约数就是2。

　　原理解析

　　那么，为什么上面运算的结果就会得到最大公约数呢？

　　我们画个图来说明。

　　

　　如图，我们分别用对应长度的线段来表示1234和678。

　　我们并不知道最大公约数是多少，但我们知道的是这两个意思数一定是最大公约数的整数倍。

　　这里我们设最大公约数为k，那么就可以把线段等分成很多小份，每一份的长度为k。

　　

　　那么，1234除以678的余数556自然也可以用刻度为k的小段来构成。

　　

　　同理，678除以556的余数122同样可以用刻度为k的小段来构成。

　　如此循环下去，直到只有1个线段k，此时余数为0。对应的线段长度就是最大公约数2。

　　

　　在计算较大数的最大公约数时，欧几里得算法是很高效的。