分数公约数的算法

‘壹’ 公约数的算法

公约数不存在什么算法，您是不是想问若干个数的最大公约数怎样计算？若是，如下：
常用的方法就是用短除式除：先看这些数，若互质，则他们的最大公约数为1；若不互质，就找出他们的公有质因数，然后用每个数去除以这个公有质因数，一直找找除除，除除找找直到除后商互质，再把所有的公有质因数乘起来，积就是这若干个数的最大公约数；若两个数成倍数关系，则最小公倍数为较小数；
不知能不能懂。呵呵，加油！不懂的话再问，诚答！

‘贰’ 求公约数的最简单方法

求公约数的最简单方法如下：

求两个正整数的最大公约数（Greatest Common Divisor，简称GCD），最简单的方法是使用欧几里得算法（又称辗转相除法）。

假设需要求出a和b的最大公约数，可以执行以下步骤：

1.比较a和b，如果a>b，则令a=a-b；否则，令b=b-a。

2.继续执行第一步，直到a=b为止。

3.最终结果即为a（也等于b）。

可以通过扩展欧几里得算法，在求解最大公约数的同时，还可以计算出两个正整数的最小公倍数（Least Common Multiple，简称LCM）。

扩展欧几里得算法的基本思想是，在每一轮欧几里得算法中，都使用较小的数去除较大的数，然后不断更新余数和被除数，直到余数为0为止。在执行这个过程时，我们记录下每一轮的商和余数，然后倒序回溯，利用这些商和余数，即可求解出最大公约数和最小公倍数。

除了欧几里得算法外，还有其他方法可以求解最大公约数和最小公倍数。例如，可以使用质因数分解法，将两个正整数分解成质因数的乘积，然后找出它们的交集和并集，从而求解出最大公约数和最小公倍数。

总之，求解最大公约数和最小公倍数是数学中的基础问题，在实际应用中非常常见。无论是使用欧几里得算法、扩展欧几里得算法，还是质因数分解法，都需要掌握好基本的数学知识和算法原理，才能快速高效地解决这些问题。

‘叁’ 求两个数的最大公约数

求两个数的最大公约数有下列几种方法：

欧几里得算法：

例如求1997和615的最大公因数的步骤：

1997/615=3（余152）。

615/152=4（余7）。

152/7=21（余5）。

7/5=1（余2）。

5/2=2(余1)。

2/1=2(余0)。

至此1997和615的最大公约数为1，以除数和余数反复做运算，最后余数为0，取当前算式除数为最大公约数，所以就得出了1997和615的最大公约数1，这是欧几里得算法。

公共积子因

算法简介：通过计算两个数字的公共积子因。

算法描述：计算gcd(m,n)

第一步:找出m的全部质因数。

第二步:找出n的全部质因数。

第三步:从第一步和第二步求得的质因数分解式中找出所有的公因数(如果p是一个公因数,而且在m和n的质因数分解式分别出现过pm和pn次,那么应该将p重复min{pm,pn}次)。

第四步:将第三步中找到的质因数相乘,其结果作为给定数字的最大公约数。