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

目录

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表示程序正常结束
}

1. 头文件：包含标准输入输出库 #include <stdio.h>。
2. 主函数：int main() 是程序的入口点。
3. 输入：使用 scanf 获取用户输入的两个整数 a 和 b。
4. 确保 a 是较大的数字：如果 a 小于 b，则交换它们的值。
5. 计算乘积：计算 a 和 b 的乘积并存储在 n 中。
6. 计算最大公约数：使用辗转相除法（欧几里得算法）计算最大公约数。
7. 输出结果：使用 printf 输出最大公约数和最小公倍数（通过 n / b 计算）。
8. 返回值：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 % bwhile r != 0:a, b = b, rr = 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(); // 关闭扫描器}
}

1. 使用 Scanner 类获取用户输入。
2. 提示用户输入两个数字，并将其存储在变量 a 和 b 中。
3. 通过条件判断确保 a 是较大的数字。
4. 计算两个数字的乘积 n。
5. 使用辗转相除法计算最大公约数。
6. 最后输出最大公约数和最小公倍数。
7. 关闭 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();

1. 使用 prompt() 函数获取用户输入，并将输入的字符串转换为整数。
2. 使用 Math.max() 和 Math.min() 确保 larger 是较大的数字，smaller 是较小的数字。
3. 计算两个数字的乘积 n。
4. 使用辗转相除法计算最大公约数。
5. 最后使用 alert() 输出最大公约数和最小公倍数。

注意：

• 该代码在浏览器环境中运行，因为它使用了 prompt() 和 alert() 函数来与用户交互。