最大公因子，又称最大公约数（英语：greatest common divisor，gcd），指两个或多个
整数共同具有的最大
约数。
定义
最大公因子，记为 或 。
求两个整数最大公约数主要的方法：
两个整数的最大公约数可用于计算两数的最小公倍数，或分数化简成
最简分数。
例子
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
#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 a % b == 0 ? b : GCD(b, a % b);}
Python
GCD = lambda a, b: (GCD(b, a % b) if a % b else b)