如何找出兩個整數的最大公因數
- 學習教育
- 關注:1.16W次
方法1:使用除數算法
1、去掉負號。
2、瞭解相關詞彙(32除以5): 32 是被除數
5 是除數
6 是商
2 是餘數(模數)
3、找兩個數較大的一個,作爲被除數。小的數作爲除數。
4、寫出公式?: (被除數) = (除數) * (商) + (餘數)
5、大的數作爲被除數,小的作爲除數。
6、得出商。
7、得出餘數,寫入公式。
8、再寫出公式,不過用上面的除數代替這裏的被除數,上面的餘數作爲除數。
9、一直重複步驟直到餘數爲零。
10、最後一個除數,就是最大公因數了。
11、這個例子中我們找出108和30的最大公因數:
12、注意第一行30和18在第二行的位置,然後除數變被除數,餘數變除數,以此類推。其中每一行的商都和其他的商意義不同,只隸屬於這一行,對其他行沒用。
方法2:利用素因數
1、去掉負號。
2、分別找出兩數的素因子分解,列出來。24和18爲例:24- 2 x 2 x 2 x 3
18- 2 x 3 x 3
50和35爲例:50- 2 x 5 x 5
35- 5 x 7
3、找出共同素因子24、18爲例24- 2 x 2 x 2 x 3
18- 2 x 3 x 3
50和35爲例50- 2 x 5 x 5
35- 5 x 7
4、素因子相乘,得出最大公因數。24和18的例子中,2乘以3得到6,即最大公因數。
50和35例子中,5是唯一的共同素因子,即最大公因數。
5、完成。
小提示
另一種方式來寫,就是被除數mod除數= 餘數。餘數爲0則GCD(最大公因數)(a,b) = b, 其他情況下GCD(a,b) = GCD(b, a mod b)比如找GCD(-77,91)。 先用77 替換 -77,GCD(-77,91) 變爲 GCD(77,91) 。 77 小於91,因此換個位置。看看是否能用公式來算。下面因爲77 mod 91得到77 (因爲 77 = 91 x 0 + 77) ,我們要的不是0作爲最大公因數,因此(a, b) 轉換爲 (b, a mod b)得到: GCD(77,91) = GCD(91,77)。 91 mod 77 得到 14 (這意味着14 是餘數) ,因爲不是0,就把GCD(91,77) 替換爲GCD(77,14) 。 77 mod 14 得到7 也不是0,再把GCD(77,14) 換成 GCD(14,7)。 14 mod 7 得到0。因爲 14 = 7 * 2 無餘數,最大公因數: GCD(-77,91) = 7
若 'a' 、 'b' 都是0,則任何非零數都是他們的公因數,所以沒有最大公因數。數學家一般就說最大公因數是0,這個就是本例中方法得到的。
可以用這種方法很有效地化簡分數。比如上述例子,-77/91 化簡爲 -11/13 因爲7是-77 、91的最大公因數。
- 文章版權屬於文章作者所有,轉載請註明 https://shqsg.com/zh-hant/xuexijiaoyu/exp9x4.html