查看“︁最大公因數”︁的源代码

{{NoteTA
|T=zh-hans:最大公因数; zh-hant:最大公因數;
|G1=Math
}}
'''最大公因-{}-數'''（{{lang-en|highest common factor}}，{{lang|en|hcf}}）也稱'''最大公約-{}-數'''（{{lang-en|greatest common divisor}}，{{lang|en|gcd}}）是[[數學]]詞彙，指能够[[整除]]多個非零[[整數]]的最大正整数。例如8和12的最大公因数为4。

最大公因数的值至少為1，例如<math>\gcd(3,7) = 1</math>；最大則為該組整數中[[绝对值|絕對值]]最小的絕對值，例如<math>\gcd(3,9) = 3</math>和<math>\gcd(-3,9) = 3</math>。

求兩個整數最大公因數主要的方法：
* [[列舉法]]：分別列出兩整數的所有[[因數]]，並找出最大的公因數。
* [[質因數分解]]：分別列出兩數的質因數分解式，並計算共同項的[[乘積]]。
* [[短除法]]：兩數除以其共同[[質因數]]，直到兩數[[互質]]時，所有除數的乘積即為最大公因數。
* [[欧几里得算法]]：<math>\gcd(a,b) = \gcd(b, a  \,\mathrm{mod}\,  b)</math>

兩個整數<math>a, b</math>的最大公因數和[[最小公倍數]]（{{lang|en|lcm}}）的關係為：
:<math>\gcd(a, b) \operatorname{lcm}(a, b) = |ab|</math>

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

兩個整數的最大公因數和最小公倍數中存在[[分配律]]：
:<math>\gcd(a, \operatorname{lcm}(b, c)) = \operatorname{lcm}(\gcd(a, b), \gcd(a, c))</math>
:<math>\operatorname{lcm}(a, \gcd(b, c)) = \gcd(\operatorname{lcm}(a, b), \operatorname{lcm}(a, c))</math>

在[[直角坐標]]中，兩[[頂點 (幾何)|頂點]]為<math>(0, 0), (a, b)</math>的線段會通過<math>\gcd(a, b)+1</math>個[[格子點]]。

== 概述 ==

=== 例子 ===
54和24的最大公因数是多少？

数字54可以表示為几组不同正整數的乘積：
:<math>54 = 1 \times 54 = 2 \times 27 = 3 \times 18 = 6 \times 9</math>

故54的正因數為<math>1, 2, 3, 6, 9, 18, 27, 54</math>。

同樣地，24可以表示為：
:<math>24 = 1 \times 24 = 2 \times 12 = 3 \times 8 = 4 \times 6</math>

故24的正因數為<math>1, 2, 3, 4, 6, 8, 12, 24</math>。

这两组数列中的共同元素即为54和24的'''[[公因数]]'''：
:<math>1, 2, 3, 6</math>

其中的最大數6即為54和24的'''最大公因數'''，記為：
:<math>\gcd(54,24) = 6</math>

=== 互质数 ===

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

=== 几何角度的说明 ===
[[File:24x60.svg|thumb|upright|alt="瘦长的矩形区域，划分成了正方形的网格，宽两格、高五格。"|24乘60的矩形被十个12乘12的正方形格子完全覆盖，即12为24和60的最大公因数。推而广之，如果''c''是''a''和''b''的最大公因数，那么''a''乘''b''的矩形就可以被若干个边长为''c''的正方形格子完全覆盖。]]

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

== 计算 ==

=== 质因数分解法 ===

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

再举一个用[[文氏图]]表示的例子，计算48和180的最大公因数。首先对这两个数进行质因数分解：
:<math>48 = 2 \times 2 \times 2 \times 2 \times 3</math>
:<math>180= 2 \times 2 \times 3 \times 3 \times 5</math>

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

:[[File:least common multiple.svg|300px]]<ref>{{Cite web |url=http://demonstrations.wolfram.com/UnderstandingTheLeastCommonMultipleAndGreatestCommonDivisor/ |title=Gustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", &#91;&#91;Wolfram Demonstrations Project&#93;&#93;, Published: February 1, 2013.  |access-date=2018-06-11 |archive-date=2020-09-22 |archive-url=https://web.archive.org/web/20200922084641/https://demonstrations.wolfram.com/UnderstandingTheLeastCommonMultipleAndGreatestCommonDivisor/ |dead-url=no }}</ref> 

: 最小公倍数<math>=2 \times 2 \times (2 \times 2 \times 3) \times 3 \times 5 =720</math>
: 最大公因数<math>=2 \times 2 \times 3 =12</math>

=== 辗转相除法 ===

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

计算<math>\gcd(18,48)</math>时，先将48除以18得到[[商数|商]]2、[[余数]]12，然后再将18除以12得到商1、余数6，再将12除以6得到商2、余数0，即得到最大公因数6。我们只关心每次除法的余数是否为0，为0即表示得到答案。这一算法更正式的描述是这样的：

:<math>\gcd(a, 0) = a</math>
:<math>\gcd(a, b) = \gcd(b, a \,\mathrm{mod}\, b)</math>

其中

:<math> a \,\mathrm{mod}\, b = a - b \left\lfloor {a \over b} \right\rfloor </math>

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

:<math>\gcd(a,a) = a</math>, 
:<math>\gcd(a,b) = \gcd(a - b,b)\quad</math> 如果 ''a'' > ''b''
:<math>\gcd(a,b) = \gcd(a, b-a)\quad</math> 如果 ''b'' > ''a''

[[File:The Great Common Divisor of 62 and 36 is 2.ogv|thumb|使用辗转相除法计算62和36的最大公因数2的演示动画。]]

== 性质 ==

* 任意''a''和''b''的公因数都是<math>\gcd(a,b)</math>的[[因數]]。
* <math>\gcd</math>函数满足[[交换律]]：<math>\gcd(a, b) = \gcd(b, a)</math>。
* <math>\gcd</math>函数满足[[结合律]]：<math>\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)</math>

== 程式代碼 ==
以下使用[[輾轉相除法]]實現。

=== C# ===
<syntaxhighlight lang="csharp" line="1">
private int GCD(int a, int b) {
	if(0 != b) while(0 != (a %= b) && 0 != (b %= a));
	return a + b;
}
</syntaxhighlight>

=== C++ ===
运行时计算实现：
<syntaxhighlight lang="cpp">
template<typename T>
T GCD(T a, T b) {
	if(b) while((a %= b) && (b %= a));
	return a + b;
}
</syntaxhighlight>
编译时计算实现：
<syntaxhighlight lang="cpp">

#include <iostream>
#include <type_traits>

template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a, std::enable_if_t<std::is_integral<T>::value, T> b>
struct HCF{
public:
    static const T value=HCF<T, (a>b? b: a), (a>b? a%b: b%a)>::value;
};
template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a>
struct HCF<T, a, 0>{
public:
    static const T value=a;
};
int main(){
    std::wcout<<HCF<int, 12, 64>::value<<std::endl;//Output: 4
}

</syntaxhighlight>

=== C ===
<syntaxhighlight lang="c">
int GCD(int a, int b) {
	if (b) while((a %= b) && (b %= a));
	return a + b;
}
</syntaxhighlight>

=== Java ===
<syntaxhighlight lang="java">
private int GCD(int a, int b) {
    if (b==0) return a; 
	return GCD(b, a % b);
}
</syntaxhighlight>

=== JavaScript ===
<syntaxhighlight lang="javascript">
const GCD = (a, b) => b ? GCD(b, a % b) : a;
</syntaxhighlight>

=== Python===
<syntaxhighlight lang="py">
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)
</syntaxhighlight>

== 政治用法 ==
{{Expand section||time=2020-08-30T17:38:36+00:00}}
{{Seealso|共識決策法|香港核心價值}}
最大公約數又指一社會中不同陣營勉強所達之共同利益。

== 参考文献 ==
{{Reflist}}

== 外部链接 ==
* [http://4rdp.blogspot.tw/2012/09/blog-post_22.html 圖解最大公因數求法] {{Wayback|url=http://4rdp.blogspot.tw/2012/09/blog-post_22.html |date=20180418204658 }}
*[https://drive.google.com/file/d/1rRXgTnFzhmZgP8Y1bcaWeVwv3z6VN_bz/view 包含GCD動態規劃] {{Wayback|url=https://drive.google.com/file/d/1rRXgTnFzhmZgP8Y1bcaWeVwv3z6VN_bz/view |date=20210909132844 }}

== 参见 ==
* [[公倍数]]
* [[公约数]]
* [[最小公倍数]]

[[Category:积性函数]]
[[Category:数论]]
[[Category:算术]]
[[Category:二元运算]]