C语言用穷举法求最大公约数最小公倍数

可以使用穷举法（也称为暴力枚举法）来求最大公约数和最小公倍数。下面是 C 语言的代码示例：

#include <stdio.h>

int main() {
    int num1, num2, i, gcd, lcm;

    printf("请输入两个正整数，用空格隔开：");
    scanf("%d %d", &num1, &num2);

    // 求最大公约数
    for(i = 1; i <= num1 && i <= num2; i++) {
        if(num1 % i == 0 && num2 % i == 0) {
            gcd = i;
        }
    }

    // 求最小公倍数
    lcm = num1 * num2 / gcd;

    printf("最大公约数：%d\n", gcd);
    printf("最小公倍数：%d\n", lcm);

    return 0;
}

在上面的代码中，我们从 1 到两个输入数中的较小者遍历，找到两个数的公约数，并将其存储在变量 `gcd` 中。最后，通过公式 `num1 * num2 / gcd` 来计算最小公倍数 `lcm`。

相关问题

c语言+最大公约数最小公倍数

C语言中求最大公约数和最小公倍数的方法有很多种，下面介绍两种常见的方法：

1. 辗转相除法

辗转相除法，也叫欧几里得算法，是求最大公约数的一种常用方法。其基本思想是：用较大数除以较小数，再用余数去除除数，如此反复，直到余数为0为止。此时，除数就是最大公约数。

代码示例：

#include <stdio.h>

int gcd(int a, int b) {
    int temp;
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    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;
}

2. 穷举法

穷举法是求最小公倍数的一种常用方法。其基本思想是：从两个数中较大的那个开始，依次枚举它的倍数，直到找到一个同时是两个数的倍数的最小正整数。

代码示例：

#include <stdio.h>

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

int lcm(int a, int b) {
    int max = a > b ? a : b;
    while (1) {
        if (max % a == 0 && max % b == 0) {
            break;
        }
        max++;
    }
    return max;
}

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;
}

用暴力穷举法求两数的最大公约数和最小公倍数

暴力穷举法是一种简单粗暴的算法，可以用来求解两个数的最大公约数和最小公倍数。具体实现方法如下：

最大公约数（GCD）的求解方法：
1. 从两个数中较小的数开始，逐个往下枚举，找到两个数都能整除的最大的数，即为最大公约数。
2. 如果两个数中有一个数为0，则另一个数即为最大公约数。

最小公倍数（LCM）的求解方法：
1. 先求出最大公约数。
2. 两个数的乘积除以最大公约数即为最小公倍数。

下面是C语言的代码实现：

#include <stdio.h>

int gcd(int a, int b) {
    int i, min, result;
    if (a == 0 || b == 0) {
        return a + b;
    }
    min = a < b ? a : b;
    for (i = min; i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            result = i;
            break;
        }
    }
    return result;
}

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

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