最大公约数与最小公倍数

发表于 | 更新于 | 分类于 ，

1. 最大公约数：gcd

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 gcd(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))