最佳答案:
最大公因子，又称最大公约数（英语：greatest common divisor，gcd），指两个或多个整数共同具有的最大约数。
详情介绍
最大公因子，又称最大公约数（英语：greatest common divisor，gcd），指两个或多个整数共同具有的最大约数。
- 中文名
- 最大公因子
- 外文名
- greatest common divisor
- 别名
- 最大公约数
- 定义
- 两个或多个整数共同有的最大约数
- 应用学科
- 数学
- 相关术语
- 最小公倍数
最大公因子定义
最大公因子，又称最大公约数（英语：greatest common divisor，gcd），指两个或多个整数共同具有的最大约数，记为
或 。求两个整数最大公约数主要的方法：
穷举法：分别列出两整数的所有约数，并找出最大的公约数。素因数分解：分别列出两数的素因数分解式，并计算共同项的乘积。短除法：两数除以其公同素因数，直到两数互素时，所有除数的乘积即为最大公约数。辗转相除法：两数相除，取余数重复进行相除，直到余数为{displaystyle 0}时，前一个除数即为最大公约数。两个整数{displaystyle a,b}的最大公约数和最小公倍数（lcm）的关系为：
两个整数的最大公约数可用于计算两数的最小公倍数，或分数化简成最简分数。
两个整数的最大公约数和最小公倍数中存在分配律：
在直角坐标中，两顶点为
的线段会通过 个格子点。最大公因子例子
54可以表示为两两不同正整数的乘积：
故54的正约数为
。同样地，24可以表示为：
故24的正约数为 。
24,54都有的正约数1,2,3,6即为公约数，其中最大的公约数6即为最大公约数，记为
。
最大公因子程式代码
数字之间的最大公约数之所有约数是该组数字所有的公约数。
以下使用辗转相除法实现。
C#
1 private int GCD(int a, int b){
2 if(0 != b) while(0 != (a %= b) && 0 != (b %= a));
3 return a + b;
4 }
C++
运行时计算实现：
template < typename T >
T GCD(T a, T b)
{ if(b) while((a %= b) && (b %= a));
return a + b;}
编译时计算实现：
#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}
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 a % b == 0 ? b : GCD(b, a % b);}
Python
GCD = lambda a, b: (GCD(b, a % b) if a % b else b)
