当前位置：首页 > article >正文

最大公约数和最小公倍数-多语言

article 2024/11/28 22:52:40

C 语言实现

Python 实现

Java 实现

Js 实现

题目：输入两个正整数m和n，求其最大公约数和最小公倍数。

程序分析：

最小公倍数=输入的两个数之积除于它们的最大公约数，关键是求出最大公约数；
求最大公约数用辗转相除法（又名欧几里德算法）

1、证明：设c是a和b的最大公约数，记为c=gcd(a,b),a>=b,
令r = a mod b
设a = kc，b = jc，则k，j互素，否则c不是最大公约数
据上，r = a-mb = kc-mjc = (k-mj)c
可知r也是c的倍数，且k-mj与j互素，否则与前述k，j互素矛盾,
由此可知，b与r的最大公约数也是c，即gcd(a,b) = gcd(b,a mod b)，得证。

2、算法描述：

第一步：a ÷ b，令r为所得余数（0≤r 第二步：互换：置 a←b，b←r，并返回第一步。

C 语言实现

#include <stdio.h>

int main() {
    int a, b, t, r;

    // 提示用户输入两个数字
    printf("请输入两个数字：\n");
    scanf("%d %d", &a, &b);

    // 确保 a 是较大的数字
    if (a < b) {
        t = b;
        b = a;
        a = t;
    }

    // 计算 a 和 b 的乘积
    int n = a * b;

    // 使用辗转相除法计算最大公约数
    r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    // 输出结果
    printf("这两个数的最大公约数是 %d，最小公倍数是 %d\n", b, n / b);

    return 0; // 返回0表示程序正常结束
}

头文件：包含标准输入输出库 #include <stdio.h>。
主函数：int main() 是程序的入口点。
输入：使用 scanf 获取用户输入的两个整数 a 和 b。
确保 a 是较大的数字：如果 a 小于 b，则交换它们的值。
计算乘积：计算 a 和 b 的乘积并存储在 n 中。
计算最大公约数：使用辗转相除法（欧几里得算法）计算最大公约数。
输出结果：使用 printf 输出最大公约数和最小公倍数（通过 n / b 计算）。
返回值：return 0; 表示程序正常结束。

这种实现方式清晰易懂，能够正确计算并输出两个数字的最大公约数和最小公倍数。

Python 实现

def main():
    # 提示用户输入两个数字
    a, b = map(int, input("请输入两个数字：\n").split())

    # 确保 a 是较大的数字
    if a < b:
        a, b = b, a

    # 计算 a 和 b 的乘积
    n = a * b

    # 使用辗转相除法计算最大公约数
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b

    # 输出结果
    print(f"这两个数的最大公约数是 {b}，最小公倍数是 {n // b}")

if __name__ == "__main__":
    main()  # 调用主函数

使用 input() 函数获取用户输入，并使用 map() 和 split() 将输入的字符串转换为两个整数。
通过条件判断确保 a 是较大的数字。
计算两个数字的乘积 n。
使用辗转相除法计算最大公约数。
最后输出最大公约数和最小公倍数

Java 实现

import java.util.Scanner;

public class GCDAndLCM {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 提示用户输入两个数字
        System.out.println("请输入两个数字：");
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        // 确保 a 是较大的数字
        if (a < b) {
            int t = b;
            b = a;
            a = t;
        }

        // 计算 a 和 b 的乘积
        int n = a * b;

        // 使用辗转相除法计算最大公约数
        int r = a % b;
        while (r != 0) {
            a = b;
            b = r;
            r = a % b;
        }

        // 输出结果
        System.out.printf("这两个数的最大公约数是 %d，最小公倍数是 %d\n", b, n / b);

        scanner.close(); // 关闭扫描器
    }
}

使用 Scanner 类获取用户输入。
提示用户输入两个数字，并将其存储在变量 a 和 b 中。
通过条件判断确保 a 是较大的数字。
计算两个数字的乘积 n。
使用辗转相除法计算最大公约数。
最后输出最大公约数和最小公倍数。
关闭 Scanner 以释放资源。

Js 实现

function calculateGCDAndLCM() {
    // 提示用户输入两个数字
    const a = parseInt(prompt("请输入第一个数字："));
    const b = parseInt(prompt("请输入第二个数字："));

    // 确保 a 是较大的数字
    let larger = Math.max(a, b);
    let smaller = Math.min(a, b);

    // 计算 a 和 b 的乘积
    const n = larger * smaller;

    // 使用辗转相除法计算最大公约数
    let r = larger % smaller;
    while (r !== 0) {
        larger = smaller;
        smaller = r;
        r = larger % smaller;
    }

    // 输出结果
    alert(`这两个数的最大公约数是 ${smaller}，最小公倍数是 ${n / smaller}`);
}

// 调用函数
calculateGCDAndLCM();