上一页

ⓘ 最大公因數




最大公因數
                                     

ⓘ 最大公因數

最大公因數 (英語: highest common factor , hcf )也稱 最大公約數 (英語: greatest common divisor , gcd )是數學詞彙,指能够整除多個整數的最大正整数。而多個整数不能都为零。例如8和12的最大公因数为4。

整数序列 a {\displaystyle a} 的最大公因数可以記為 {\displaystyle a_{1},a_{2},\dots,a_{n}} 或 gcd {\displaystyle \gcda_{1},a_{2},\dots,a_{n}} 。

求兩個整數最大公因數主要的方法:

  • 質因數分解:分別列出兩數的質因數分解式,並計算共同項的乘積。
  • 短除法:兩數除以其共同質因數,直到兩數互質時,所有除數的乘積即為最大公因數。
  • 窮舉法:分別列出兩整數的所有因數,並找出最大的公因數。
  • 輾轉相除法:兩數相除,取餘數重複進行相除,直到餘數為 0 {\displaystyle 0} 時,前一個除數即為最大公因數。

兩個整數 a, b {\displaystyle a,b} 的最大公因數和最小公倍數( lcm )的關係為:

gcd a, b lcm ⁡ a, b = | a b | {\displaystyle \gcda,b\operatorname {lcm} a,b=|ab|}

兩個整數的最大公因數可用於計算兩數的最小公倍數,或分數化簡成最簡分數。

兩個整數的最大公因數和最小公倍數中存在分配律:

gcd a, lcm ⁡ b, c) = lcm ⁡ gcd a, b, gcd a, c) {\displaystyle \gcda,\operatorname {lcm} b,c)=\operatorname {lcm} \gcda,b,\gcda,c)} lcm ⁡ a, gcd b, c) = gcd lcm ⁡ a, b, lcm ⁡ a, c) {\displaystyle \operatorname {lcm} a,\gcdb,c)=\gcd\operatorname {lcm} a,b,\operatorname {lcm} a,c)}

在直角坐標中,兩頂點為 0, 0, a, b {\displaystyle 0.0,a,b} 的線段會通過 gcd a, b + 1 {\displaystyle \gcda,b+1} 個格子點。

                                     

1. 概述

互质数

如果两数的最大公因数为1,那么这两个数互質。例如,9和28就是互质数。

                                     

1.1. 概述 互质数

如果两数的最大公因数为1,那么这两个数互質。例如,9和28就是互质数。

                                     

1.2. 概述 几何角度的说明

假设有一个大小为24乘60的矩形区域,这个区域可以按照不同的大小划分正方形网格:1乘1、2乘2、3乘3、4乘4、6乘6、12乘12。因此,12是24和60的最大公因数。大小为24乘60的矩形区域,可以按照12乘12的大小划分正方形网格,一边有两格( 24 12 = 2 {\displaystyle {\frac {24}{12}}=2} )、另一边有五格( 60 12 = 5 {\displaystyle {\frac {60}{12}}=5} )。

                                     

2.1. 计算 质因数分解法

可以通过質因數分解来计算最大公因数。例如计算 gcd 18, 84 {\displaystyle \gcd18.84} ,可以先进行质因数分解 18 = 2 × 3 2 {\displaystyle 18=2\times 3^{2}} 和 84 = 2 × 3 × 7 {\displaystyle 84=2^{2}\times 3\times 7} ,因为其中表达式 2 × 3 {\displaystyle 2\times 3} 的「重合」,所以 gcd 18, 84 = 6 {\displaystyle \gcd18.84=6} 。实践中,这种方法只在数字比较小时才可行,因为对较大数进行质因数分解通常会耗费大量的时间。

再举一个用文氏图表示的例子,计算48和180的最大公因数。首先对这两个数进行质因数分解:

48 = 2 × 2 × 2 × 2 × 3 {\displaystyle 48=2\times 2\times 2\times 2\times 3} 180 = 2 × 2 × 3 × 3 × 5 {\displaystyle 180=2\times 2\times 3\times 3\times 5}

它们之中的共同元素是两个2和一个3:

最小公倍数 = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720 {\displaystyle =2\times 2\times 2\times 2\times 3\times 3\times 5=720} 最大公因数 = 2 × 2 × 3 = 12 {\displaystyle =2\times 2\times 3=12}
                                     

2.2. 计算 辗转相除法

相比质因数分解法,辗转相除法的效率更高。

计算 gcd 18, 48 {\displaystyle \gcd18.48} 时,先将48除以18得到商2、余数12,然后再将18除以12得到商1、余数6,再将12除以6得到商2、余数0,即得到最大公因数6。我们只关心每次除法的余数是否为0,为0即表示得到答案。这一算法更正式的描述是这样的:

gcd a, 0 = a {\displaystyle \gcda,0=a} gcd a, b = gcd b, a m o d b {\displaystyle \gcda,b=\gcdb,a\,\mathrm {mod} \,b}

其中

a m o d b = a − b ⌊ a b ⌋ {\displaystyle a\,\mathrm {mod} \,b=a-b\left\lfloor {a \over b}\right\rfloor }

如果参数都大于0,那么该算法可以写成更简单的形式:

gcd a, a = a {\displaystyle \gcda,a=a}, gcd a, b = gcd a − b, b {\displaystyle \gcda,b=\gcda-b,b\quad } 如果 a > b gcd a, b = gcd a, b − a {\displaystyle \gcda,b=\gcda,b-a\quad } 如果 b > a
                                     

3. 性质

  • gcd {\displaystyle \gcd } 函数满足交换律: gcd a, b = gcd b, a {\displaystyle \gcda,b=\gcdb,a} 。
  • gcd {\displaystyle \gcd } 函数满足结合律: gcd a, gcd b, c) = gcd a, b, c) {\displaystyle \gcda,\gcdb,c)=\gcd\gcda,b,c)}
  • 任意 a 和 b 的公因数都是 gcd a, b {\displaystyle \gcda,b} 的因數。
                                     

4. 程式代碼

數字之間的最大公因數之所有因數是該組數字所有的公因數。

以下使用輾轉相除法實現。

C++

运行时计算实现:

编译时计算实现: