例子

54可以拆分为两个不同的整数：

54的约数有：

同样地，24的约数有：

两个列表内都有的数字为公约数：

最大的数字是6。54和24的最大公约数是6。

程式代码

数字之间的最大公约数之所有约数是该组数字所有的公约数。

以下使用辗转相除法实现。

C#

1 privateintGCD(inta,intb){2 if(0!=b)while(0!=(a%=b)&&0!=(b%=a));3 returna+b;4 }

C++

运行时计算实现：

templateTGCD(Ta,Tb){if(b)while((a%=b)&&(b%=a));returna+b;}

编译时计算实现：

#include#includetemplate<typenameT,std::enable_if_t<std::is_integral::value,T>a,std::enable_if_t<std::is_integral::value,T>b>structHCF{public:staticconstTvalue=HCFb?b:a),(a>b?a%b:b%a)>::value;};template<typenameT,std::enable_if_t<std::is_integral::value,T>a>structHCF{public:staticconstTvalue=a;};intmain(){std::wcout<<HCF::value<<std::endl;//Output: 4}

C

intGCD(inta,intb){if(b)while((a%=b)&&(b%=a));returna+b;}

JAVA

privateintGCD(inta,intb){if(b==0)returna;returna%b==0?b:GCD(b,a%b);}

Python

GCD=lambdaa,b:(GCD(b,a%b)ifa%belseb)

参见

公倍数

公约数

最小公倍数

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。