c++求最大公约数的方法有哪些

c++

575

2024/3/20 14:42:03

栏目: 编程语言

辗转相除法（欧几里得算法）：通过连续求两个数的余数和除数之间的商，直到余数为0，即可得到最大公约数。

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

更相减损术：通过连续减小的两个数，直到它们相等为止，即可得到最大公约数。

int gcd(int a, int b) {
    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

递归法：通过递归的方式求解最大公约数。

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

这些方法都可以用来求解最大公约数，其中辗转相除法是最常用的一种方法。

辰迅云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

c++求最大公约数的方法有哪些

最新知识库

相关标签