计算两个非负整数的最大公约数

公约数也是公因数，如果一个数可以同时整除几个数，那么这个数就是这个几个数的公约数。

比如 3 可以整除 3，6，12 ，那么 3 就是 3，6， 12 的共约数。

比如两个数(m,n)的最大公约数是 k 。 那么有 m = x*k , n = y*k。 并且 x 和 y 互为质数。假设 m > n

m-n = (x-y) *k , 所以可以得出结论 m,n的公约数和 m,n, m-n 的三个数的，问题就变成 球 （n, 和 m-n) 的最大公约数是相同的。

这样的减法可以操作多次，减法执行多次后，最后剩下其实是 余数。

比如要计算 28, 和 36 的最大公约数。

1. 28, 36 —> 36,28->28,(36-28)->28,8->8,(28-8) -> 8, 20
2. 20,8->8,12->12,8->8,4->4

可以看到结果是 4 。

辗转相除法（欧几里得算法)

辗转相除法总结

1. 如果两个整数 p, q 若 q = 0 ,则最大的公约数是 p。
2. 若 q 不等于 0， r 为 p除以q的余数。 p, q 的最大公约数等于 q 和 r 的最大公约数。

运行代码

#include <stdio.h>

unsigned int f(unsigned int p, unsigned int q) {
    unsigned int ans;
    if(q == 0) {
        return p;
    }

    if(p < q) {
        return f(q, p);
    }
    return f(q, p%q);
}


unsigned int f2(unsigned int p, unsigned int q) {
    // 保证 p 大于 q
    if(p < q) return f(q, p);

    // 如果 p 是 q 的倍数， 返回 q
    if(p%q == 0) {
        return q;
    }

    // 文件转换成  q ,和 p-q 两数的最大公约数
    return f(q, p-q);
}

int main() {
    printf("%u\n", f(36, 28));
    printf("%u\n", f2(36, 28));
    return 0;
}