求字的最大公约数

辗转相除法

image.png

java代码实现

1
2
3
4
5
6
7
8
private static int gcd(int a, int b) {
    while (a % b != 0) {
        int  z = a % b;
        a = b;
        b = z;
    }
    return b;
}

求多个数的最大公约数

对于多个数的最大公约数，大概是这么一个情况

image.png
先求出前面的数的最大公约数，得到的结果和后面的数继续求最大公约数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static int gcd(int[] nums) {
    int num = nums[0];
    for (int i = 1; i < nums.length; i++) {
        num = gcd(num, nums[i]);
    }
    return num;
}

private static int gcd(int a, int b) {
    while (a % b != 0) {
        int  z = a % b;
        a = b;
        b = z;
    }
    return b;
}

为什么可以这样

对于多个数求最大公约数，先把每个数变成质数相乘的形式

63 = 3 * 3 * 7

18 = 2 * 3 * 3

9 = 3 * 3

45 = 5 * 3 * 3

求他们的最大公约数，无非就是找到他们相同的质数

image.png

对于找n个数的相同的质数部分，是不是就等于找到前n-1个数的质数相同的部分以后，再和当前数找最大相同质数部分。

这里说得不是很清，水平有限😢