In this java program, you’ll learn how to find the HCF(Highest Common Factor) or GCD (Greatest Common Divisor). In this program, we will use two different methods to find the HCF or GCD: using Loops and Library Function.
Java Program to Find HCF or GCD of Two Numbers Using the Euclidean Algorithm and Recursion
Java Program to Find HCF or GCD of Two Numbers Using Recursion
An HCF or GCD of two or more numbers is the largest positive integer that divides each of the numbers. For example, the HCF or GCD of 10 and 12 is 2.
Here is the code of the program to find the HCF(Highest Common Factor) or GCD (Greatest Common Divisor) using for loop.
// Java Program to Find GCD of two Numbers
import java.util.Scanner;
public class JavaPrograms {
public static void main(String[] args) {
// scanner class declaration
Scanner sc = new Scanner(System.in);
// input from the user
System.out.print("Enter the first number : ");
int num1 = sc.nextInt();
// input from the user
System.out.print("Enter the second number : ");
int num2 = sc.nextInt();
int n = 1;
System.out.print("HCF of " + num1 + " and " + num2 + " is ");
if (num1 != num2) {
while (n != 0) {
// storing remainder
n = num1 % num2;
if (n != 0) {
num1 = num2;
num2 = n;
}
}
// result
System.out.println(num2);
} else
System.out.println("Wrong Input");
// closing scanner class(not compulsory, but good programming practice)
sc.close();
}
}Enter the first number : 48
Enter the second number : 18
HCF of 48 and 18 is 6
// Java Program to Find GCD of two Numbers using For Loop
import java.util.Scanner;
public class JavaPrograms {
public static void main(String[] args) {
// scanner class declaration
Scanner sc = new Scanner(System.in);
// input from the user
System.out.print("Enter the first number : ");
int num1 = sc.nextInt();
// input from the user
System.out.print("Enter the second number : ");
int num2 = sc.nextInt();
int GCD = 1, i;
// For Loop for iteration to find the GCF of both program
for (i = 1; i <= num1 && i <= num2; i++) {
/*
* Checking the modulation with both numbers against Iteration values
*/
if (num1 % i == 0 && num2 % i == 0) {
// Replacing the GCD value with the higher Iteration value
GCD = i;
}
}
System.out.print("HCF of " + num1 + " and " + num2 + " is " + GCD);
// closing scanner class(not compulsory, but good programming practice)
sc.close();
}
}Enter the first number : 48
Enter the second number : 64
HCF of 48 and 64 is 16
// Java Program to Find GCD of two Numbers Using Library Function
import java.util.Scanner;
import java.math.*;
public class JavaPrograms {
public static void main(String[] args) {
// scanner class declaration
Scanner sc = new Scanner(System.in);
// input from the user
System.out.print("Enter the first number : ");
BigInteger num1 = sc.nextBigInteger();
// input from the user
System.out.print("Enter the second number : ");
BigInteger num2 = sc.nextBigInteger();
//Getting the GCD of numbers using in-built function of math library called gcd()
BigInteger GCD = num1.gcd(num2);
System.out.print("HCF of " + num1 + " and " + num2 + " is " + GCD);
// closing scanner class(not compulsory, but good programming practice)
sc.close();
}
}Enter the first number : 48
Enter the second number : 6
HCF of 48 and 6 is 6
Comments