Java program to print HCF (GCD) of two numbers

In java, to print HCF or Highest Common Factor (GCD) of two numbers we can use loop concepts such as while loop or for loop. For a given two values, we have to print largest/ highest common multiple of those two numbers. If the input numbers are 12 and 16, factors of 12 are 1,2,3,4,6 and 12 and factors of 16 are 1,2,4,8,16. Therefore, the output is 4, as 4 is the largest/highest common factor of 12 and 16.

In this article we will learn through an example, detailed logic and program explanation for better understanding.

Required Knowledge

• Java programming basics
• Java operators
• Loop Concepts

Problem Statement

We have to write a java program to print HCF (GCD) of two numbers. The program should take two integer numbers in variable like number1 and number2 and should print the common highest factor/multiple of those two numbers. This action will be done in our program. Let’s see an example,

Example:

For input numbers 4 and 8, output should be 4.

Explanation:

Input integer number num = 4 

Input integer number num1 = 8

Factors of 4 = 1,2,4

Factors of 8 = 1,2,4,8

Common factors of 4 and 8: 1,2 and 4

Highest factor/multiple of 4 and 8: 4

Hence, the highest factor which will divide the 4 and 8 without having any remainder is 4.

Logic to print HCF of two numbers

• Take two input numbers as number1 and number2 from the user.
• Initialize hcf to 0. This variable will store the highest common factor found during the iteration.
• Use a loop (while or for loop) to iterate through all possible factors of number1 and number2 starting from 1 (i=1).
• The loop condition i<=number1 and i<=number2, ensures that i does not exceed either of the numbers.
• Inside the loop, the program checks if i is a common factor of both number1 and number2 using the if conditional statement number1%i==0 && number2%i==0.
• If i is a common factor, it assigns the value of i to hcf.
• After the loop completes, the value of hcf will be the greatest common factor of number1 and number2 and program will print the result.

Java program to print HCF of two numbers

Program 1: Using while loop

In the below program we are using while loop to print HCF/GCD of two numbers in Java.

import java.util.Scanner;
public class GCDOfTwo {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("Enter first number");
		int number1 = sc.nextInt();
		System.out.println("Enter second number");
		int number2 = sc.nextInt();
		int hcf=0;
		int i=1;
		while(i<=number1 && i<=number2) {
			if(number1%i==0 && number2%i==0)
				hcf=i;
			i++;
		}
		System.out.println("HCF of given two numbers are: "+hcf);
		sc.close();
	}
}

Output:

Enter first number
345
Enter second number
546
HCF of given two numbers are: 3

Java program explanation to print hcf of two numbers

1. The above java program imports the Scanner class to read input from the user.
2. In the main method:
   • It creates a Scanner object sc to read input from the user.
   • Asks the user to enter the first number.
   • Reads the first number entered by the user.
   • Asks the user to enter the second number.
   • Reads the second number entered by the user.
   • Initializes the variable hcf to store the highest common factor, initially set to 0.
   • Initializes the variable i to 1, which will be used as an iterator.
   • Enters a while loop that continues as long as i is less than or equal to both number1 and number2.
   • Checks if both number1 and number2 are divisible by the current value of i without any remainder.
   • If both are divisible, updates the hcf variable with the current value of i.
   • Increments i to move on to the next potential factor.
   • After the loop completes, prints out the calculated HCF.
   • Closes the Scanner object to release system resources.

Program 2: Using for loop

In the below program we are using for loop to print hcf of two numbers in Java.

import java.util.Scanner;
public class GCDOfTwo {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("Enter first number");
		int number1 = sc.nextInt();
		System.out.println("Enter second number");
		int number2 = sc.nextInt();
		int hcf = 0;
		for (int i = 1; i <= number1 && i <= number2; i++) {
			if (number1 % i == 0 && number2 % i == 0)
				hcf = i;
		}
		System.out.println("HCF of given two numbers are: " + hcf);
		sc.close();
	}
}

Output:

Enter first number
1125
Enter second number
225
HCF of given two numbers are: 225

Java program explanation to print hcf of two numbers

1. The java program imports the Scanner class to read input from the user.
2. In the main method:
   • It creates a Scanner object sc to read input from the user.
   • Asks the user to enter the first number.
   • Reads the first number entered by the user.
   • Asks the user to enter the second number.
   • Reads the second number entered by the user.
   • Initializes the variable hcf to store the highest common factor, initially set to 0.
   • Enters a for loop that iterates from 1 to the minimum of the two numbers (number1 and number2).
   • Checks if both number1 and number2 are divisible by the current value of i without any remainder.
   • If both are divisible, updates the hcf variable with the current value of i.
   • After the loop completes, prints out the calculated HCF.
   • Closes the Scanner object to release system resources.

Conclusion

In this article, we have learnt how to print HCF of two numbers in Java. We have seen the logic and understood the program using while loop in Java and for loop in Java. Hope this article helped you in the understanding of the program.

You can also check our another awesome tutorials

• Java program to print sum of odd numbers in a range
• Check if a number is perfect or not in Java
• Count the digits of a given number in Java
• Java Program to check if a number is divisible by 11

Happy Programming!