最大公约数

什么是最大公约数？

最大公约数 的本质是一个最大的能同时被两整数整除的自然数

求最大公约数的方法

暴力法

原理：先比较两数大小，从较小数开始向下递增，直至找到最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
    int a = 12;
    int b = 16;
    int i = 0;
    if (a > b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    for (i = a; i > 0; i--)
    {
        if (a % i == 0 && b % i == 0)
        {
            printf("%d is greatest common divisor", i);
            break;
        }
    }
    return 0;
}

辗转相除法（欧几里得法）

image-20221209172951603

原理：用较大数除较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。最后的除数就是这两个数的最大公约数。（以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数）

在这个代码中，首先将 a 和 b 两个数分别赋给变量 a 和 b，然后用 while 循环进行辗转相除，将 a 除以 b 得到余数 c，如果 c 不为 0，则将 b 赋值给 a，将 c 赋值给 b，然后继续进行下一次循环。当 c 为 0 时，此时 b 就是 a 和 b 的最大公约数，最后输出 b。
需要注意的是，这个程序也没有考虑 a 和 b 为负数或零的情况，需要在实际使用时做出相应的处理。同时，这个程序也没有考虑 a 和 b 的大小关系，因此需要在程序开始时使用 if 语句将 a 和 b 两个数进行排序，保证 a 是小的数，b 是大的数，以确保算法正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    int a = 3139;
    int b = 1022;
    int c = 0;
    while (c = a % b)
    {
        a = b;
        b = c;
    }
    printf("%d is greatest common divisor", b);
    return 0;
}

辗转相减法

原理： 取两个数中的较大的数做减数，较小的数做被减数，用大的数减去小数，直至除数与被除数相等。（大减小，直至相等）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    int a = 3139;
    int b = 1022;
    int c = 0;
    while (a != b)
    {
        if (a < b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
        c = a - b;
        a = b;
        b = c;
    }
    printf("%d is greatest common divisor", a);
    return 0;
}