最大公因-{}-數（，）也稱最大公約-{}-數（，）是數學詞彙，指能够整除多個非零整數的最大正整数。例如8和12的最大公因数为4。
最大公因数的值至少為1，例如\gcd(3,7) = 1；最大則為該組整數中絕對值最小的絕對值，例如\gcd(3,9) = 3和\gcd(-3,9) = 3。
求兩個整數最大公因數主要的方法：
- 列舉法：分別列出兩整數的所有因數，並找出最大的公因數。
- 質因數分解：分別列出兩數的質因數分解式，並計算共同項的乘積。
- 短除法：兩數除以其共同質因數，直到兩數互質時，所有除數的乘積即為最大公因數。
- 欧几里得算法：\gcd(a,b) = \gcd(b, a \,\mathrm{mod}\, b)
兩個整數a, b的最大公因數和最小公倍數（）的關係為：
:\gcd(a, b) \operatorname{lcm}(a, b) = |ab|
兩個整數的最大公因數可用於計算兩數的最小公倍數，或分數化簡成最簡分數。
兩個整數的最大公因數和最小公倍數中存在分配律：
:\gcd(a, \operatorname{lcm}(b, c)) = \operatorname{lcm}(\gcd(a, b), \gcd(a, c))
:\operatorname{lcm}(a, \gcd(b, c)) = \gcd(\operatorname{lcm}(a, b), \operatorname{lcm}(a, c))
在直角坐標中，兩頂點為(0, 0), (a, b)的線段會通過\gcd(a, b)+1個格子點。
概述
例子
54和24的最大公因数是多少？
数字54可以表示為几组不同正整數的乘積：
:54 = 1 \times 54 = 2 \times 27 = 3 \times 18 = 6 \times 9
故54的正因數為1, 2, 3, 6, 9, 18, 27, 54。
同樣地，24可以表示為：
:24 = 1 \times 24 = 2 \times 12 = 3 \times 8 = 4 \times 6
故24的正因數為1, 2, 3, 4, 6, 8, 12, 24。
这两组数列中的共同元素即为54和24的公因数：
:1, 2, 3, 6
其中的最大數6即為54和24的最大公因數，記為：
:\gcd(54,24) = 6
互质数
如果两数的最大公因数为1，那么这两个数互質。例如，9和28就是互质数。
几何角度的说明
假设有一个大小为24乘60的矩形区域，这个区域可以按照不同的大小划分正方形网格：1乘1、2乘2、3乘3、4乘4、6乘6、12乘12。因此，12是24和60的最大公因数。大小为24乘60的矩形区域，可以按照12乘12的大小划分正方形网格，一边有两格（\frac{24}{12}=2）、另一边有五格（\frac{60}{12}=5）。
计算
质因数分解法
可以通过質因數分解来计算最大公因数。例如计算\gcd(18, 84)，可以先进行质因数分解 18 = 2 \times 3^2 和 84 = 2^2 \times 3 \times 7，因为其中表达式2 \times 3的「重合」，所以\gcd(18, 84) = 6。实践中，这种方法只在数字比较小时才可行，因为对较大数进行质因数分解通常会耗费大量的时间。
再举一个用文氏图表示的例子，计算48和180的最大公因数。首先对这两个数进行质因数分解：
:48 = 2 \times 2 \times 2 \times 2 \times 3
:180= 2 \times 2 \times 3 \times 3 \times 5
它们之中的共同元素是两个2和一个3：
:
: 最小公倍数=2 \times 2 \times (2 \times 2 \times 3) \times 3 \times 5 =720
: 最大公因数=2 \times 2 \times 3 =12
辗转相除法
相比质因数分解法，辗转相除法的效率更高。
计算\gcd(18,48)时，先将48除以18得到商2、余数12，然后再将18除以12得到商1、余数6，再将12除以6得到商2、余数0，即得到最大公因数6。我们只关心每次除法的余数是否为0，为0即表示得到答案。这一算法更正式的描述是这样的：
:\gcd(a, 0) = a
:\gcd(a, b) = \gcd(b, a \,\mathrm{mod}\, b)
其中
: a \,\mathrm{mod}\, b = a - b \left\lfloor {a \over b} \right\rfloor
如果参数都大于0，那么该算法可以写成更简单的形式：
:\gcd(a,a) = a,
:\gcd(a,b) = \gcd(a - b,b)\quad 如果 a > b
:\gcd(a,b) = \gcd(a, b-a)\quad 如果 b > a
性质
- 任意a和b的公因数都是\gcd(a,b)的因數。
- \gcd函数满足交换律：\gcd(a, b) = \gcd(b, a)。
- \gcd函数满足结合律：\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)
程式代碼
以下使用輾轉相除法實現。
C#
private int GCD(int a, int b) {
if(0 != b) while(0 != (a %= b) && 0 != (b %= a));
return a + b;
}
C++
运行时计算实现：
template
T GCD(T a, T b) {
if(b) while((a %= b) && (b %= a));
return a + b;
}
编译时计算实现：
#include
#include
template::value, T> a, std::enable_if_t::value, T> b>
struct HCF{
public:
static const T value=HCFb? b: a), (a>b? a%b: b%a)>::value;
};
template::value, T> a>
struct HCF{
public:
static const T value=a;
};
int main(){
std::wcout::value
C
int GCD(int a, int b) {
if (b) while((a %= b) && (b %= a));
return a + b;
}
Java
private int GCD(int a, int b) {
if (b==0) return a;
return GCD(b, a % b);
}
JavaScript
const GCD = (a, b) => b ? GCD(b, a % b) : a;
Python
GCD = lambda a, b: (a if b == 0 else GCD(b, a % b))
or
def GCD(a, b):
if b == 0:
return a
return GCD(b, a % b)
政治用法
最大公約數又指一社會中不同陣營勉強所達之共同利益。
参考文献
外部链接
*[https://drive.google.com/file/d/1rRXgTnFzhmZgP8Y1bcaWeVwv3z6VN_bz/view 包含GCD動態規劃]
参见
- 公倍数
- 公约数
- 最小公倍数
评论 (0)