求最大公因数和最小公倍数（C++实现）

2024-09-01 22:24:35

求两个正整数之最大公因子的算法（辗转相除法）

最大公约数是指能同时整除它们的最大正整数

基本原理：两个数的最大公约数等于它们中较小的数和两数之差的最大公约数。

就如有 a = 122, b = 54,a与b 的最大公约数也是54 与（122 - 54）的最大公约数；

即有:

122 54

68 54

54 14

40 14

......

2 0

代码有：

int GreatestCommonDivisor(int a, int b)

{

int t;

if (a < b)

{

temp = a;

a = b;

b = t;

}

while (b != 0)

{

t = a % b;

a = b;

b = t;

}

return a;

}

求最小公倍数是可依靠最大公因数

设c是a与b的最大公因数

int LeastCommonMultiple (int a, int b)

{

int t = a * b /c;

return t;

}

最新文章

热门文章