1.1 基础

一般我们都是使用辗转相除法来求最大公约数，该算法被称为欧几里得算法(gcd)。

两个正整数a和b (a > b)，它们的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数

换而言之:

[
left{
begin{aligned}
&gcd(a, b) = gcd(b, a mod b )& (a > b not = 0)\
&gcd(a, 0) = a
end{aligned}
right.
]

这样我们可以写出简单的递归式:

1
2
3
4

private static int (int a, int b)
{
    return (b == 0)? a : gcd(b, a % b);
}

可以证明以上的递归是 (O(log{n})) 级别的，所以无须担心爆栈。

1.2 多个数的最大公约数:multiGcd

其实这个算法完全可以用递归的思想来解决:

1
2
3
4
5
6
7

private static int multiGcd(int[] arr, int n)
{
    if (n == 1)
        return arr[0];
    else
        return gcdLauncher(arr[n-1], multiGcd(arr, n-1));
}

2. 最小公倍数: lcm

2.1 基础

有公式: [
gcd(a, b) cdot lcm(a, b) = a cdot b
]

1
2
3
4
5

private static int lcm(int a, int b)
{
    
    return a / gcd(a, b) * b;
}

2.2多个数的最小公倍数:multiLcm

同理:

1
2
3
4
5

def multiLcm(arr, n):
    if n == 1:
         return arr[0]
    else:
        return lcm(arr[n-1], multiLcm(arr, n-1))