最大公因數

互素数

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

几何角度的说明

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

程式代码

数字之间的最大公约数之所有约数是该组数字所有的公约数。
以下使用辗转相除法实现。

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)

政治用法

最大公约数又指一社会中不同阵营勉强所达之共同利益。