Java Program to Calculate GCD of two numbers

In this tutorial, we will learn how to find the Greatest Common Divisor( GCD ) of two numbers in java. The Highest Common Factor(HCF) or Greatest Common Divisor(GCD) of two or more numbers is defined as the greatest number which divides each of them exactly. But before moving forward if you are not familiar with the concept of loops in java, then do check the article on Loops in Java.

Input: Enter the first number: 3

Enter the second number: 5

Output: HCF of the two numbers 3 and 5 is 1

Program 1: Java Program to Calculate the GCD of two Numbers

In this program, we will see how to calculate the GCD of two numbers in java by using for loop.

Algorithm:

1. Start
2. Create an instance of the Scanner class.
3. Declare two variables.
4. Ask the user to initialize these variables.
5. Declare a variable to store the HCF and initialize it to 0.
6. Use a for loop to calculate the GCD.
7. If both the numbers are divisible by the loop variable, then set the number to the GCD.
8. Continue the process till the largest number which divides both the numbers without remainder is found.
9. Print the result.
10. Stop.

//Java Program to Calculate the GCD of two numbers
import java.util.Scanner;  
public class Main   
{  
    public static void main(String[] args)    
    {
        //Take input from the user
        //Create an instance of the Scanner class
        Scanner sc = new Scanner(System.in); 
        System.out.println("Enter the first number: ");  
        int num1 = sc.nextInt();  
        System.out.println("Enter the second number: ");  
        int num2 = sc.nextInt();  
        int hcf=0;
        for(int i = 1; i <= num1 || i <= num2; i++) 
        {
         if( num1%i == 0 && num2%i == 0 )
         hcf = i;
      }
      System.out.println("HCF of given two numbers is :"+hcf);
   }  
}  

Enter the first number: 2
Enter the second number: 6
HCF of given two numbers is:2

Program 2: Java Program to Calculate the GCD of two Numbers

In this program, we will see how to calculate the GCD of two numbers in java by using a while loop.

Algorithm:

1. Start
2. Create an instance of the Scanner class.
3. Declare two variables.
4. Ask the user to initialize these variables.
5. Use a while loop to calculate the GCD.
6. Subtract the smaller integer from the larger integer, and assign the result to the variable holding larger integer
7. Continue the process till both the numbers are equal.
8. Print the result.
9. Stop.

//Java Program to Calculate the GCD of two numbers
import java.util.Scanner;  
public class Main   
{  
    public static void main(String[] args)    
    {
        //Take input from the user
        //Create an instance of the Scanner class
        Scanner sc = new Scanner(System.in); 
        System.out.println("Enter the first number: ");  
        int num1 = sc.nextInt();  
        System.out.println("Enter the second number: ");  
        int num2 = sc.nextInt();  
        while(num1 != num2) 
        {
          if(num1 > num2) 
          {
            num1 -= num2;
          }
          else 
          {
            num2 -= num1;
          }
        }
      System.out.println("HCF of given two numbers is :"+num1);
   }  
}  

Enter the first number: 2
Enter the second number: 7
HCF of given two numbers is :1

Program 3: Java Program to Calculate the GCD of two Numbers

In this program, we will see how to calculate the GCD of two numbers in java by using a while loop when the numbers are either positive or negative.

Algorithm:

1. Start
2. Create an instance of the Scanner class.
3. Declare two variables.
4. Ask the user to initialize these variables.
5. First set both the numbers as positive.
6. Use a while loop to calculate the GCD.
7. Subtract the smaller integer from the larger integer, and assign the result to the variable holding larger integer
8. Continue the process till both the numbers are equal.
9. Print the result.
10. Stop.

//Java Program to Calculate the GCD of two numbers
import java.util.Scanner;  
public class Main   
{  
    public static void main(String[] args)    
    {
        //Take input from the user
        //Create an instance of the Scanner class
        Scanner sc = new Scanner(System.in); 
        System.out.println("Enter the first number: ");  
        int num1 = sc.nextInt();  
        System.out.println("Enter the second number: ");  
        int num2 = sc.nextInt();  
         num1 = ( num1 > 0) ? num1 : -num1;
         num2 = ( num2 > 0) ? num2 : -num2;
        while(num1 != num2) 
        {
          if(num1 > num2) 
          {
            num1 -= num2;
          }
          else 
          {
            num2 -= num1;
          }
        }
        
      System.out.println("HCF of given two numbers is :"+num1);
   }  
}  

Enter the first number: -12
Enter the second number: 6
HCF of given two numbers is:6