最大公因数
最大公因数
最大公因-{}-数（，--
）也称最大公约-{}-数（，--
）是数学词汇，指能够整除多个整数的最大正整数。而多个整数不能都为零。例如8和12的最大公因数为4。
整数序列formula_1的最大公因数可以记为formula_2或formula_3。
求两个整数最大公因数主要的方法：
两个整数formula_4的最大公因数和最小公倍数（--
）的关系为：
formula_5
两个整数的最大公因数可用于计算两数的最小公倍数，或分数化简成最简分数。
两个整数的最大公因数和最小公倍数中存在分配律：
formula_6
formula_7
在直角坐标中，两顶点为formula_8的线段会通过formula_9个格子点。
概述.
例子.
54和24的最大公因数是多少？
数字54可以表示为几组不同正整数的乘积：
formula_10
故54的正因数为formula_11。
同样地，24可以表示为：
formula_12
故24的正因数为formula_13。
这两组数列中的共同元素即为54和24的公因数：
formula_14
其中的最大数6即为54和24的最大公因数，记为：
formula_15
互质数.
如果两数的最大公因数为1，那么这两个数互质。例如，9和28就是互质数。
几何角度的说明.
假设有一个大小为24乘60的矩形区域，这个区域可以按照不同的大小划分正方形网格：1乘1、2乘2、3乘3、4乘4、6乘6、12乘12。因此，12是24和60的最大公因数。大小为24乘60的矩形区域，可以按照12乘12的大小划分正方形网格，一边有两格（formula_16）、另一边有五格（formula_17）。
计算.
质因数分解法.
可以通过质因数分解来计算最大公因数。例如计算formula_18，可以先进行质因数分解 formula_19 和 formula_20，因为其中表达式formula_21的「重合」，所以formula_22。实践中，这种方法只在数字比较小时才可行，因为对较大数进行质因数分解通常会耗费大量的时间。
再举一个用文氏图表示的例子，计算48和180的最大公因数。首先对这两个数进行质因数分解：
formula_23
formula_24
它们之中的共同元素是两个2和一个3：
最小公倍数formula_25
最大公因数formula_26
辗转相除法.
相比质因数分解法，辗转相除法的效率更高。
计算formula_27时，先将48除以18得到商2、余数12，然后再将18除以12得到商1、余数6，再将12除以6得到商2、余数0，即得到最大公因数6。我们只关心每次除法的余数是否为0，为0即表示得到答案。这一算法更正式的描述是这样的：
formula_28
formula_29
其中
formula_30
如果参数都大于0，那么该算法可以写成更简单的形式：
formula_31,
formula_32 如果 "a" > "b"
formula_33 如果 "b" > "a"
程式代码.
以下使用辗转相除法实现。
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;
编译时计算实现：
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«HCF::value«std::endl;//Output: 4
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))
def GCD(a, b):
if b == 0:
return a
return GCD(b, a % b)
政治用法.
最大公约数又指一社会中不同阵营勉强所达之共同利益。
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.