Java Program to Compute GCD

In the previous article, we have seen Java Program to Find the Roots of Quadratic Equation

In this article we are going to see how to find the GCD using Java programming language.

Java Program to Compute GCD

Before Jumping into the program directly let’s know what is this GCD.

Greatest Common Divisor:

Greatest Common Divisor (GCD) also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF) of two integers 'a' and 'b' is defined to be the the largest integer that divides both 'a' and 'b' with no remainder.

Examples:

Let a and b are two numbers. a = 20 b = 30 Common factors of (20,30) = 1, 2, 5, 10 So, GCD = 10

Let’s see different ways to find the GCD.

General Approach with Static Input Values
General Approach with User Input Values
By Using Euclidean Repeated Subtraction Approach

Method-1: Java Program to Compute GCD By Using General Approach with Static Input Values

Approach:

Declare an int variable say ‘a’ and assign the value to it, which holds the value of the first number.
Declare an double variable say ‘b’ and assign the value to it, which holds the value of the second number.
Declare an int variable say ‘GCD’ and initialize it to 1.
Then take a for loop starting from i=1 to i=n where n is the smaller number between ‘a’ and ‘b’.
Check largest integer that divides both a and b with no remainder and print the result.

Program:

import java.io.*;
public class Main
{
    public static void main(String [] args)
    {
        //Two numbers are declared
        int a = 20;
        int b = 10;
        //integer variable GCD declared to hold GCD value
        //also initualized to 1
        int GCD =  1; 
        
        //checking the smaller number between a and b
        //and assigning the smaller number to variable n
        int n=0;
        if(a<b)
            n=a;
        else
            n=b;
    
        //Here i is the factor of n
        //since the 1st factor of any number is 1. Hence we have initialized it to 1.
        //loop will go upto 'n' which holds the smaller number between 'a' and 'b'
        for(int i = 1; i<=n; i++) 
        {
            //Checking largest integer that divides both a and b with no remainder
        	if(a%i == 0 && b%i==0)
        		GCD = i;
        }
        System.out.println("The GCD of ("+ a + "," + b + ") is: " + GCD);
    }
}

Output:

The GCD of (20,10) is: 10

Method-2: Java Program to Compute GCD By Using General Approach with User Input Values

Approach:

Declare an int variable say ‘a’ which holds the value of the first number.
Declare an double variable say ‘b’ which holds the value of the second number.
Take the value of a and b as user input by using Scanner class.
Declare an int variable say ‘GCD’ and initialize it to 1.
Then take a for loop starting from i=1 to i=n where n is the smaller number between ‘a’ and ‘b’.
Check largest integer that divides both a and b with no remainder and print the result.

Program:

import java.util.*;
public class Main
{
    public static void main(String [] args)
    {
        Scanner sc=new Scanner(System.in);
        //taking input of two numbers from user
        System.out.println("Enter two numbers:");
        int a = sc.nextInt();
        int b = sc.nextInt();
        //integer variable GCD declared to hold GCD value
        //also initualized to 1
        int GCD =  1; 
        
        //checking the smaller number between a and b
        //and assigning the smaller number to variable n
        int n=0;
        if(a<b)
            n=a;
        else
            n=b;
    
        //Here i is the factor of n
        //since the 1st factor of any number is 1. Hence we have initialized it to 1.
        //loop will go upto 'n' which holds the smaller number between 'a' and 'b'
        for(int i = 1; i<=n; i++) 
        {
            //Checking largest integer that divides both a and b with no remainder
        	if(a%i == 0 && b%i==0)
        		GCD = i;
        }
        System.out.println("The GCD of ("+ a + "," + b + ") is: " + GCD);
    }
}

Output:

Enter two numbers:
10
20
The GCD of (10,20) is: 10

Method-3: Java Program to Compute GCD By Using Euclidean Repeated Subtraction Approach

Approach:

Declare an int variable say ‘a’ and assign the value to it, which holds the value of the first number.
Declare an double variable say ‘b’ and assign the value to it, which holds the value of the second number.
Declare an int variable say ‘GCD’ and initialize it to 1.
Then we will find the GCD using Euclidean repeated subtraction.
Print the result.

Program:

public class Main
{
public static int GCD(int a, int b)
    {
        if (b == 0)
            return a;
        // here the GCD() method is called recursively 
        // by replacing a with b, and b with (a-b)  till b != 0
        else
            return GCD(b, a - b);
    }
    
    public static void main(String [] args)
    {
        int a = 20;
        int b = 10; 
        System.out.println("GCD = " + GCD(a, b));
    }

}

Output: GCD = 10

Provided list of Simple Java Programs is specially designed for freshers and beginners to get familiarize with the concepts of Java programming language and become pro in coding.

Related Java Programs: