C语言求最大公约数与最小公倍数

发布于 / C语言 / Comments Off on C语言求最大公约数与最小公倍数

最大公约数

用递归写,炒鸡简单:

int gcd(int t1, int t2) {
    return t2 == 0 ? t1 : gcd(t2, t1 % t2);
}

原理:辗转相除法。计算t1和t2的最大公约数,即求t2与t1÷t2余数的最大公约数,除到t2==0为止。

最小公倍数

要先定义上面的gcd函数,然后再定义最小公倍数函数:

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

转载原创文章请注明,转载自: 斐斐のBlog » C语言求最大公约数与最小公倍数
评论已关闭