c 辗转相除法求最大公约数和最小公倍数

辗转相除法（又称欧几里得算法）可以用来求两个数的最大公约数，具体步骤如下：

1. 用较大的数除以较小的数，得到余数r。
2. 如果r为0，则较小的数就是最大公约数。
3. 如果r不为0，则用较小的数除以r，得到余数r1。
4. 如果r1为0，则r就是最大公约数。
5. 如果r1不为0，则重复步骤3和步骤4，直到余数为0。

最小公倍数可以通过最大公约数来计算，具体公式为：

最小公倍数 = 两数之积 / 最大公约数

以下是使用C语言实现辗转相除法求最大公约数和最小公倍数的代码：

#include <stdio.h>

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

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

int main() {
    int a, b;
    printf("请输入两个整数：");
    scanf("%d %d", &a, &b);
    printf("最大公约数为：%d\n", gcd(a, b));
    printf("最小公倍数为：%d\n", lcm(a, b));
    return 0;
}

相关问题

C语言辗转相除法计算最大公约数和最小公倍数

以下是使用C语言辗转相除法计算最大公约数和最小公倍数的示例代码：

#include <stdio.h>

int main() {
    int a, b, temp, gcd, lcm;

    printf("Enter two positive integers: ");
    scanf("%d %d", &a, &b);

    // 辗转相除法求最大公约数
    int x = a, y = b;
    while (y != 0) {
        temp = x % y;
        x = y;
        y = temp;
    }
    gcd = x;

    // 计算最小公倍数
    lcm = (a * b) / gcd;

    printf("GCD of %d and %d is %d\n", a, b, gcd);
    printf("LCM of %d and %d is %d\n", a, b, lcm);

    return 0;
}

运行结果：

Enter two positive integers: 12 18
GCD of 12 and 18 is 6
LCM of 12 and 18 is 36

输入两个正整数，利用辗转相除法求最大公约数和最小公倍数

辗转相除法，也叫欧几里得算法，是求最大公约数的一种方法。具体步骤如下：
1. 输入两个正整数a和b（a>b）。
2. 用a除以b，得到商q和余数r。
3. 若r=0，则b即为最大公约数。
4. 若r≠0，则用b除以r，得到商q1和余数r1。
5. 若r1=0，则r即为最大公约数。
6. 若r1≠0，则继续用r除以r1，得到商q2和余数r2。
7. 重复上述步骤，直到余数为0为止。

最小公倍数可以通过最大公约数求得，公式为：a*b/最大公约数(a,b)。

具体代码如下：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

a = int(input("请输入第一个正整数："))
b = int(input("请输入第二个正整数："))

print("最大公约数为：", gcd(a, b))
print("最小公倍数为：", lcm(a, b))