求公因子演算法設計技術

⑴ 程序設計-求最大公因數

本文使用 歐幾里得演算法 來求 最大公因數 。

即，15和35的最大公因數為5。因為15 = 3 x 5 35 = 7 x 5 = 35 它們能夠同時被5整除

此時余數為0 除數為9 則（36，81）得最大公因數為9.

1⃣️ 計算余數和除數
大數除小數得余 去放到下一層計算

2⃣️ 確定終止條件
其中一個為0，則返回另一個 此數則為最大公因數

⑵ 怎麼求最大公因數

1、列舉法

8和12的公因數，可以分別列舉出8和12的所有因數， 再找一找。

8的因數:1，2，4，8。

12的因數:1，2，3，4，6，12。

8和12的公因數有1，2，4，其中最大的是4。

也可以先找出8的因數，再從8的因數中找12的因數。

8的因數:1，2，4，8。

其中1，2, 4也是12的因數。

8和12的公因數有1, 2，4，其中最大的是4。

2、輾轉相除法（歐幾里得演算法）

輾轉相除法是先用兩個數中較大的數除以較小的數，如果有餘數，則用較小的那個數繼續除以余數，按照這樣的方法一直除下去，除到余數為0為止，那麼最後的除數就是兩個數的最大公因數。

(2)求公因子演算法設計技術擴展閱讀

輾轉相除法與更相減損術的區別

（1）都是求最大公因數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。

（2）從結果體現形式來看，輾轉相除法體現結果是以相除余數為0則得到，而更相減損術則以減數與差相等而得到。

⑶ 求最大公因數和最小公倍數的幾種方法

求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。
求最大公約數主要有分解質因數法、公式法。
一、最大公因數求法
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、短除法
短除法：短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
短除法求最小公倍數，先用這幾個數的公約數去除每個數，再用部分數的公約數去除，並把不能整除的數移下來，一直除到所有的商中每兩個數都是互質的為止，然後把所有的除數和商連乘起來，所得的積就是這幾個數的最小公倍數，例如，求12、15、18的最小公倍數。
3、輾轉相除法
輾轉相除法：輾轉相除法是求兩個自然數的最大公約數的一種方法，也叫歐幾里德演算法。兩個整數的最大公約數等於其中較小的那個數和兩數的相除余數的最大公約數。
4、更相減損法
劉徽《九章算術》
更相減損法：也叫更相減損術，是出自《九章算術》的一種求最大公約數的演算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。
《九章算術》是中國古代的數學專著，其中的「更相減損術」可以用來求兩個數的最大公約數，即「可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。」
翻譯成現代語言如下：
第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。
第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，並以大數減小數。繼續這個操作，直到所得的減數和差相等為止。
則第一步中約掉的若干個2與第二步中等數的乘積就是所求的最大公約數。
二、最小公倍數演算法
1、分解質因數法
先把這幾個數的質因數寫出來，最小公倍數等於它們所有的質因數的乘積（如果有幾個質因數相同，則比較兩數中哪個數有該質因數的個數較多，乘較多的次數）。
2、公式法
由於兩個數的乘積等於這兩個數的最大公約數與最小公倍數的積。即（a，b）×[a，b]=a×b。所以，求兩個數的最小公倍數，就可以先求出它們的最大公約數，然後用上述公式求出它們的最小公倍數。
例如，求[18，20]，即得[18，20]=18×20÷（18，20）=18×20÷2=180。求幾個自然數的最小公倍數，可以先求出其中兩個數的最小公倍數，再求這個最小公倍數與第三個數的最小公倍數，依次求下去，直到最後一個為止。最後所得的那個最小公倍數，就是所求的幾個數的最小公倍數。
三、最大公因數、最小公倍數簡介
1、最大公因數
也稱最大公約數、最大公因子，指兩個或多個整數共有約數中最大的一個。a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c），多個整數的最大公約數也有同樣的記號。求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。與最大公約數相對應的概念是最小公倍數，a，b的最小公倍數記為[a，b]。
2、最小公倍數
兩個或多個整數的公倍數里最小的那一個叫做它們的最小公倍數。整數a，b的最小公倍數記為[a，b]，同樣的，a，b，c的最小公倍數記為[a，b，c]，多個整數的最小公倍數也有同樣的記號。

⑷ 求最大公因數的三種方法

、使用分解質因數法：把幾個數分解成幾個質因數的積，然後找相同的質因數，再把這幾個質因數相乘，積就是他們的最大公因數。
2、使用短除法：用短除法對要求公因數的數組一直往下除，除到不能再被整除為止，這樣在短除法運算過程中產生的除數就是要求的公因數了，其中最大的就是最大公因數。