用辗转相除法求最大公约数

以下是使用辗转相除法求最大公约数的Python代码：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

其中，a和b为两个非负整数，函数返回它们的最大公约数。

举个例子，如果要求48和60的最大公约数，可以这样调用函数：

print(gcd(48, 60)) # 输出：12

相关问题

用辗转相除法求最大公约数c语言

辗转相除法，也称为欧几里得算法，是一种古老的求解两个正整数最大公约数（Greatest Common Divisor，GCD）的有效方法。在C语言中，可以按照以下步骤实现：

#include <stdio.h>

// 函数声明，返回两个整数的最大公约数
int gcd(int a, int b);

// 主函数
int main() {
    int num1, num2;
    printf("请输入两个正整数：");
    scanf("%d %d", &num1, &num2);
    
    // 如果b为0，说明a就是最大公约数
    if (num2 == 0) {
        printf("两数的最大公约数是：%d\n", num1);
    } else { // 否则，递归调用gcd函数
        int result = gcd(num1, num2);
        printf("两数的最大公约数是：%d\n", result);
    }

    return 0;
}

// 辗转相除法计算GCD的函数
int gcd(int a, int b) {
    if (b == 0)
        return a; // 当b为零时结束递归，a即为结果
    else
        return gcd(b, a % b); // 把较小的数赋给b，较大的数对较小数取余，然后继续这个过程
}

在这个程序中，`gcd`函数通过不断将较大数替换为两数相除的余数，直到余数变为0，此时的非余数值即为最大公约数。

利用C语言用辗转相除法求最大公约数

以下是利用C语言用辗转相除法求最大公约数的代码：

#include <stdio.h>
int main() {
    int a, b, t;
    scanf("%d %d", &a, &b);
    while (b != 0) {
        t = a % b;
        a = b;
        b = t;
    }
    printf("%d", a);
    return 0;
}

这段代码中，我们输入两个数a和b，然后利用while循环进行辗转相除，直到b为0时，此时a的值就是最大公约数。这种方法比较高效，时间复杂度为O(logn)。

--相关问题--:
1. 什么是最大公约数和最小公倍数？
2. C语言中如何进行输入