最大公約數和公倍數演算法

1. 最大公因數和最小公倍數怎麼求

最大公因數常見求法分為質因數分解法、短除法、輾轉相除法、更相減損法;最小公倍數的求法為分解質因數法和公式法。

最大公因數求法
質因數分解法：把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數。
短除法：短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
輾轉相除法：輾轉相除法是求兩個自然數的最大公約數的一種方法，也叫歐幾里德演算法。
更相減損法：也叫更相減損術，是出自《九章算術》的一種求最大公約數的演算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。

最小公倍數求法
分解質因數法：先把這幾個數的質因數寫出來，最小公倍數等於它們所有的質因數的乘積(如果有幾個質因數相同，則比較兩數中哪個數有該質因數的個數較多，乘較多的次數)。
公式法：由於兩個數的乘積等於這兩個數的最大公約數與最小公倍數的積。即(a，b)×[a，b]=a×b。所以，求兩個數的最小公倍數，就可以先求出它們的最大公約數，然後用上述公式求出它們的最小公倍數。

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、短除法
短除法：短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
短除法求最小公倍數，先用這幾個數的公約數去除每個數，再用部分數的公約數去除，並把不能整除的數移下來，一直除到所有的商中每兩個數都是互質的為止，然後把所有的除數和商連乘起來，所得的積就是這幾個數的最小公倍數，例如，求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]，多個整數的最小公倍數也有同樣的記號。

3. 求兩個數的最大公約數和最小公倍數的演算法

分別把兩個數做質因數分解,
把相同質因數跳出來,取兩者較小的次冪乘起來,就是最大公約數
兩個數的積除以最大公約數,就是最小公倍數
比如說12和40
12=2^2*3
40=2^3*5
最大公約數=2^2=4
最小公倍數=12*40/4=120

4. 最小公倍數和最大公約數怎麼算

首先給出定義，最大公約數指幾個自然數公有的約數中最大的一個；最小公倍數指幾個自然數公有的倍數中最小的一個大於零的公倍數
舉例說明：5、9、12的最小公倍數是180
5=5，9=3*3,12=3*4,9和12有一個公約數3，寫成相乘的形式只出現一次即5*3*3*4=180，所以最小公倍數為180
例如，12和30的公約數有：1、2、3、6，其中6就是12和30的最大公約數。

5. 最大公倍數和最小公約數是怎麼計算的，有公式嗎

首先更正一下，是最大公約數、最小公倍數。

最大公約數，也稱最大公因數、最大公因子，指兩個或多個整數共有約數中最大的一個。

最小公倍數，如果有一個自然數a能被自然數b整除，則稱a為b的倍數，b為a的約數，對於兩個整數來說，指該兩數共有倍數中最小的一個。計算最小公倍數時，通常會藉助最大公約數來輔助計算

沒有具體的公式，都是要把兩個數的質因數寫出來，可以用這種方法來算：

最小公倍數等於它們所有的質因數的乘積（如果有幾個質因數相同，則比較兩數中哪個數有該質因數的個數較多，乘較多的次數）。

請參見http://..com/link?url=nQYxVn_LZ0q5SGvpzBeU04z9G-eGOh7hLCaGa4-

6. 最大公約數和最小公倍數怎麼求

你好！解法一時說不清 下面是在網路找的 希望對你有所幫助！ 1.公約數和最大公約數
幾個數公有的約數，叫做這幾個數的公約數；其中最大的一個，叫做這幾個數的最大公約數。
例如：12的約數有：1，2，3，4，6，12；
18的約數有：1，2，3，6，9，18。
12和18的公約數有：1，2，3，6.其中6是12和18的最大公約數，記作（12，18）=6。
2.公倍數和最小公倍數
幾個數公有的倍數，叫做這幾個數的公倍數；其中最小的一個，叫做這幾個數的最小公倍數。
例如：12的倍數有：12，24，36，48，60，72，84，…
18的倍數有：18，36，54，72，90，…
12和18的公倍數有：36，72，….其中36是12和18的最小公倍數， 這樣求最小公倍數 首先把兩個數的質因數寫出來，最小公倍數等於它們所有的質因數的乘積（如果有幾個質因數相同，則比較兩數中哪個數有該質因數的個數較多，乘較多的次數）。
比如求45和30的最小公倍數。
45=3*3*5
30=2*3*5
不同的質因數是2,3,5。3是他們兩者都有的質因數，由於45有兩個3，30隻有一個3，所以計算最小公倍數的時候乘兩個3.
最小公倍數等於2*3*3*5=90 又如計算36和270的最小公倍數
36=2*2*3*3
270=2*3*3*3*5
不同的質因數是5。2這個質因數在36中比較多，為兩個，所以乘兩次；3這個質因數在270個比較多，為三個，所以乘三次。
最小公倍數等於2*2*3*3*3*5=540
這樣求最大公約數
法一、 短除法求最大公因數的一種方法，也可用來求最小公倍數。
求幾個數最大公因數的方法，開始時用觀察比較的方法，即：先把每個數的因數找出來，然後再找出公因數，最後在公因數中找出最大公因數。
例如：求12與18的最大公因數。
12的因數有：1、2、3、4、6、12。
18的因數有：1、2、3、6、9、18。
12與18的公因數有：1、2、3、6。
12與18的最大公因數是6。
這種方法對求兩個以上數的最大公因數，特別是數目較大的數，顯然是不方便的。 法二、 分解質因數法 於是又採用了給每個數分別分解質因數的方法。
12＝2×2×3
18＝2×3×3
12與18都可以分成幾種形式不同的乘積，但分成質因數連乘積就只有以上一種，而且不能再分解了。所分出的質因數無疑都能整除原數，因此這些質因數也都是原數的約數。從分解的結果看，12與18都有公因數2和3，而它們的乘積2×3＝6，就是12與18的最大公因數。
採用分解質因數的方法，也是採用短除的形式，只不過是分別短除，然後再找公因數和最大公因數。如果把這兩個數合在一起短除，則更容易。
從短除中不難看出，12與18都有公因數2和3，它們的乘積2×3＝6就是12與18的最大公因數。與前邊分別分解質因數相比較，可以發現：不僅結果相同，而且短除法豎式左邊就是這兩個數的公共質因數，而兩個數的最大公因數，就是這兩個數的公共質因數的連乘積。
說到這里，請再求出12和18的最小公倍數 12＝2×2×3
18＝2×3×3
即12和18的最小公倍數=2*2*3*3=36 而12和18的最大公約數=2*3=6 附：有這一公式可以幫助：（只是在一般情況下適用） 兩數的乘積=它們的最大公約數*它們的最小公倍數 如：12*18=36*6

7. 怎樣求最大公約數和最小公倍數

• 在掌握最小公倍數和最大公因數主要使用下面兩個有用的工具：

  1、分解素因數法

  2、短除法

  

8. 最大公約數和最小公倍數的求法，快！

求最大公約數一般先用這兩個數公有的質因數去除，一直除到所有的商是互質數為止，然後把所有的商連乘起來。。比如說30和24的最大公約數是是6.具體用短除法。。

9. 最大公約數和最大公倍數怎麼運算啊

最大公約數 最小公倍數 都用的是短除法
比如 求4，6,12,的最大公約數為2 ， 最小公倍數為24
最大公倍數有無數個