分數公約數的演算法

『壹』 公約數的演算法

公約數不存在什麼演算法，您是不是想問若干個數的最大公約數怎樣計算？若是，如下：
常用的方法就是用短除式除：先看這些數，若互質，則他們的最大公約數為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}次)。

第四步:將第三步中找到的質因數相乘,其結果作為給定數字的最大公約數。