上查看所有课程
两个整数的HCF或GCD是能整除两个数（无余数）的最大整数。
示例1：使用for循环和if语句查找两个数的GCD
class Main {
public static void main(String[] args) {
// find GCD between n1 and n2
int n1 = 81, n2 = 153;
// initially set to gcd
int gcd = 1;
for (int i = 1; i <= n1 && i <= n2; ++i) {
// check if i perfectly divides both n1 and n2
if (n1 % i == 0 && n2 % i == 0)
gcd = i;
}
System.out.println("GCD of " + n1 +" and " + n2 + " is " + gcd);
}
}输出
GCD of 81 and 153 is 9
这里，要查找GCD的两个数分别存储在n1和n2中。
然后，执行一个for循环，直到i小于n1和n2。这样，迭代1到两个数中较小数之间的所有数字来查找GCD。
如果n1和n2都能被i整除，则gcd被设置为该数字。这会一直持续到找到能整除n1和n2且无余数的最大数字（GCD）。
我们也可以使用while循环来解决这个问题，如下所示：
示例2：使用while循环和if else语句查找两个数的GCD
class Main {
public static void main(String[] args) {
// find GCD between n1 and n2
int n1 = 81, n2 = 153;
while(n1 != n2) {
if(n1 > n2) {
n1 -= n2;
}
else {
n2 -= n1;
}
}
System.out.println("GCD: " + n1);
}
}输出
GCD: 9
这是查找GCD的更好方法。在此方法中，将较小的整数从较大的整数中减去，并将结果赋给保存较大整数的变量。此过程一直持续到n1和n2相等为止。
上面的两个程序仅在用户输入正整数时才按预期工作。下面是对第二个示例进行的小修改，用于查找正负整数的GCD。
示例3：正负数GCD
class GCD {
public static void main(String[] args) {
int n1 = 81, n2 = -153;
// Always set to positive
n1 = ( n1 > 0) ? n1 : -n1;
n2 = ( n2 > 0) ? n2 : -n2;
while(n1 != n2) {
if(n1 > n2) {
n1 -= n2;
}
else {
n2 -= n1;
}
}
System.out.println("GCD: " + n1);
}
}输出
GCD: 9
另请阅读