Java求两个数的最大公约数
以下是几种在Java中求两个数最大公约数(GCD)的方法：
（图片来源网络，侵删）
使用欧几里得算法（辗转相除法）
public class GCD {
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
int num1 = 48;
int num2 = 18;
System.out.println("最大公约数是: " + gcd(num1, num2)); // 输出: 6
}
}
递归实现欧几里得算法
public class GCD {
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
public static void main(String[] args) {
int num1 = 48;
int num2 = 18;
System.out.println("最大公约数是: " + gcd(num1, num2)); // 输出: 6
}
}
使用Java 8的Math类（Java 9+）
public class GCD {
public static void main(String[] args) {
int num1 = 48;
int num2 = 18;
// Java 9+ 提供了gcd方法
int gcd = Math.floorDiv(num1, num2); // 这是错误的，正确用法如下
// 正确用法：
int gcd = java.math.BigInteger.valueOf(num1).gcd(java.math.BigInteger.valueOf(num2)).intValue();
System.out.println("最大公约数是: " + gcd); // 输出: 6
}
}
处理负数的情况
如果需要处理负数,可以在计算前取绝对值：
public class GCD {
public static int gcd(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
int num1 = -48;
int num2 = 18;
System.out.println("最大公约数是: " + gcd(num1, num2)); // 输出: 6
}
}
处理大数的情况
对于非常大的整数,可以使用BigInteger类：
import java.math.BigInteger;
public class GCD {
public static void main(String[] args) {
BigInteger num1 = new BigInteger("12345678901234567890");
BigInteger num2 = new BigInteger("98765432109876543210");
BigInteger gcd = num1.gcd(num2);
System.out.println("最大公约数是: " + gcd);
}
}
方法中，欧几里得算法是最常用且高效的实现方式，时间复杂度为O(log(min(a,b)))。
（图片来源网络，侵删）
