求***公约数最快方法

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

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

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

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

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

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

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

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

怎样求***公约数？

您好，在求***公约数时,一般先用最小的公约数去除,直到得数为互质数时为止,再将所有的公约数相乘,积就是几个数的***公约数。

举个例子：

以12和16为例，两者先都除以2，得6,8。

6和8还可以继续除以2，得到3,4。

3,4互为质数，不可再除。

所以12,和16的***公约数就等于2乘2，得4。

***公因数，也称*** 公约数、***公 因子，指两个或多个 整数共有 约数中***的一个。 a， b的***公约数记为（a，b），同样的，a，b，c的*** 公约数记为（a，b，c），多个 整数的***公约数也有同样的记号。求***公约数有多种 方法，常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。与***公约数相对应的概念是 最小公倍数，a，b的 最小公倍数记为[a，b]。

求***公约数的简便方法

求***公约数的简便方法如下：

1、辗转相除法（欧几里德法）C语言中用于计算两个正整数a，b的***公约数，采用函数嵌套调用形式进行求两个数的***公约数。其算法过程为：

前提：设两数为a，b设其中a做被除数，b做除数，temp为余数；Steps：大数放a中，小数放b中；求a/b的余数；若temp=0则b为***公约数。如果temp！=0则把b的值给a,temp的值给a。

2、穷举法（枚举法）

从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是***公约数。

3、更相减损法

Steps：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则***步中约掉的若干个2与第二步中等数的乘积就是所求的***公约数。

4、Stein算法

性质：gcd（kx，ky）=k*gcd（x，y）。

对两个正整数 xy。

均为偶数gcd（x，y）=2gcd（x/2，y/2）。

均为奇数gcd（x，y）=gcd（（x+y）/2，（x-y）/2）。

X奇y偶gcd（x，y）=gcd（x-y）/2）。

X偶y奇gcd（x，y）=gcd（x/2，y）。

或gcd（x，y）=gcd（y，x/2）。

***公约数怎么求算法

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

1、质因数分解法

把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的***公约数。

例如：求24和60的***公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）＝12。

2、短除法

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

3、辗转相除法

辗转相除法也叫欧几里德算法。用辗转相除法求几个数的***公约数，可以先求出其中任意两个数的***公约数，再求这个***公约数与第三个数的***公约数，依次求下去，直到最后一个数为止。最后所得的那个***公约数，就是所有这些数的***公约数。

4、更相减损法

也叫更相减损术，是出自《九章算术》的一种求***公约数的算法，它原本是为约分而设计的，但它适用于任何需要求***公约数的场合。

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的***公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

***步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则***步中约掉的若干个2与第二步中等数的乘积就是所求的***公约数。

其中所说的“等数”，就是***公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

扩展欧几里德算法

扩展欧几里得算法（又称扩充欧几里得算法）是用来解某一类特定的不定方程的一种方法，常用用来求解模线性方程及方程组。扩展的欧几里得算法可以用来计算模逆元，而模逆元在公钥密码学中占有举足轻重的地位。

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的***公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

最大公约数怎么求的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于最大公约数怎么求?、最大公约数怎么求的信息别忘了在本站进行查找喔。