java求最大公约数（GCD）与最小公倍数（LCM）

本文主要是介绍java求最大公约数（GCD）与最小公倍数（LCM），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求最大公约数（GCD）与最小公倍数（LCM）

含义解释

最大公约数（GCD）：
- 两个或多个整数共有的约数中最大的一个。例如，12和18的最大公约数是6。
- 对于两个非零整数a和b，它们的最大公约数是能够同时整除a和b的最大正整数。记为gcd(a, b)。
最小公倍数（LCM）：
- 两个或多个整数公有的倍数中最小的一个。例如，4和6的最小公倍数是12。
- 对于两个非零整数a和b，它们的最小公倍数是能够同时被a和b整除的最小正整数。记为lcm(a, b)。

数学推导证明

最大公约数（GCD）：可以使用辗转相除法（欧几里德算法）来计算最大公约数。辗转相除法的基本思想是利用余数的不断相除，直到余数为0时，所得除数即为最大公约数。推导证明略。
最小公倍数（LCM）：可以通过最大公约数的性质来计算最小公倍数。由于两个数的乘积等于它们的最大公约数与最小公倍数的积，所以可以通过最大公约数来计算最小公倍数。推导证明略。

4. Java代码实现

下面是使用Java实现GCD和LCM的示例代码：

public class GCD_LCM {// 求最大公约数（GCD）// 写法一 （要求a<b）public static int gcd(int a, int b) {while (b != 0) {int temp = a % b;a = b;b = temp;}return a;}// 写法二public static int gcd(int a, int b) {return b == 0 ? a : gcd(b,a%b);}// 求最小公倍数（LCM）// 写法一（a*b可能导致int溢出）public static int lcm(int a, int b) {return a * b / gcd(a, b);}//写法二（先除再乘，防止int溢出）public static int lcm(int a, int b) {return a / gcd(a, b)*b;}public static void main(String[] args) {int num1 = 12;int num2 = 18;// 计算最大公约数int gcdResult = gcd(num1, num2);System.out.println("最大公约数：" + gcdResult);// 计算最小公倍数int lcmResult = lcm(num1, num2);System.out.println("最小公倍数：" + lcmResult);}
}