Java Program to Find GCD of Two Numbers

GCD stands for Greatest Common Divisor. GCD of two numbers in Java is the largest positive integer that completely divides both the given numbers.

Example: GCD(10,15) = 15, GCD(12,15) = 3.

Write a Java Program to Find the GCD of two numbers.

1. Take two numbers as input.
2. Start a loop from 2 to the minimum of two integers m and n and find out their common divisor.
3. Print the output.

There are several ways to find the GCD of two numbers in Java language. Let’s look at all different approaches to write a Java program to calculate the GCD of two numbers.

• GCD of Two Numbers in Java using Loops
• GCD of Two Numbers in Java Without Using Recursion
• GCD of Two Numbers in Java using Euclid’s Algorithm

In this approach, we find the GCD of two numbers using a loops.

Here is the source code of the Java Program to Calculate GCD of 2 Given Numbers Using loops. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

/* 
 * GCD of Two Numbers in Java using Loops
 */
 
import static java.lang.StrictMath.min;
import java.util.Scanner;
public class GCD
{
    public static void main(String args[])
    {
        int a, b, hcf = 1;
        Scanner s = new Scanner(System.in);
        System.out.print("Enter First Number:");
        a = s.nextInt();
        System.out.print("Enter Second Number:");
        b = s.nextInt();
        int n = min(a,b);
        for(int i = 2; i < n; i++)
        {
            while(a % i == 0 && b % i==0)
            {
                hcf = hcf * i;
                a = a / i;
                b = b / i;
            }
        }
        System.out.println("Greatest Common Divisor:"+hcf);
    }
}

1. Define a public class called “GCD” that contains a main method.
2. Declare three integer variables “a“, “b“, and “hcf“. “a” and “b” will hold the user input, and “hcf” will be used to store the GCD of the two numbers.
3. Prompt the user to enter the first number and read it from the console using the nextInt() method.
4. Prompt the user to enter the second number and read it from the console using the nextInt() method.
5. Find the minimum of the two numbers using the “min” method and store it in a new variable “n“.
6. Use a for loop to iterate from 2 to “n“.
7. Use a while loop to repeatedly divide both “a” and “b” by the current value of “i” as long as they are both divisible by “i“.
8. If “a” and “b” are both divisible by “i“, multiply “hcf” by “i“.
9. Divide “a” and “b” by “i” after every successful division in the while loop.
10. When the loop is finished, print out the GCD of the two numbers using the value of “hcf“.

Testcase 1: The numbers entered by the user to calculate gcd in this case are 24 and 16.

$ javac GCD.java
$ java GCD
 
Enter First Number:24
Enter Second Number:16
Greatest Common Divisor:8

Testcase 2: The numbers entered by the user to calculate gcd in this case are 50 and 20.

$ javac GCD.java
$ java GCD
 
Enter First Number: 50
Enter Second Number: 20
Greatest Common Divisor:10

This approach finds the GCD of two numbers using a for loop without recursion.

Here is the source code of the Java Program to Calculate GCD of 2 Given Numbers Without Using recursion. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

 
//Java Program to Calculate GCD of 2 Given Numbers Without Using recursion
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class GCDWithoutRecursion {
    // Function to read two integers and find their gcd
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int i1,j1;
        System.out.println("Enter the two numbers");
        try{
            i1=Integer.parseInt(br.readLine());
            j1=Integer.parseInt(br.readLine());
        }catch (Exception e){
            System.out.println("An error occurred");
            return;
        }
        if(i1 == 0 || j1 == 0){
            System.out.println("The greatest common divisor is " + 1);
            return;
        }
        int i;
        int gcd = 1;
        for(i=2; i<=Math.min(i1,j1); i++){
            if(i1%i == 0 && j1%i == 0){
                gcd = i;
            }
        }
        System.out.println("The greatest common divisor is " + gcd);
    }
}

In the function main(), firstly the two integers m and n are entered and then using the loop for(i=2; i<=Math.min(i1,j1); i++), the common divisor is searched. Finally, the gcd is displayed.

Time Complexity: O(min(a, b))
The time complexity of the program is O(min(a, b)), where a and b are the two input integers. This is because the program uses a for loop to iterate through all the possible values of the GCD (i.e., integers between 2 and the minimum of a and b) and check if they divide both a and b.

Space Complexity: O(1)
The space complexity of the program is O(1), which means that the amount of memory required by the program remains constant, regardless of the size of the input numbers.

Testcase 1: The numbers entered by the user to calculate gcd in this case are 894 and 2334.

Enter the two numbers
894
2334
The greatest common divisor is 6

Testcase 2: The numbers entered by the user to find gcd using recursion are 50 and 20.

Enter the two numbers
50
20
The greatest common divisor is 10.

In this approach we find the GCD of Two Numbers Using Euclid’s Algorithm. Euclid’s Algorithm is an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest numerical algorithms in common use.

Steps to find GCD of Two Numbers using Euclid’s Algorithm
1. Divide the two numbers entered by the user and remainder become divisor while previous divisor become dividend now.
2. This process repeat until the remainder become zero and we get the GCD as divisor which gives remainder as zero.

Here is the source code of the Java Program to find GCD and LCM of Two Numbers Using Euclid’s Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/*
 * GCD of Two Numbers in Java Using Euclids Algorithm
 */
 
import java.util.Scanner;
public class Euclid
{
    void gcd(long a, long b)
    {
        while (b > 0)
        {
             long temp = b;
             b = a % b; // % is remainder
             a = temp;
        }
        System.out.println("GCD is "+a);
    }
        public static void main(String... a)
    {
        Euclid abc = new  Euclid();
        System.out.println("Enter any two numbers to calculate GCD");
        Scanner s = new Scanner(System.in);
        long x = s.nextLong();
        long y = s.nextLong();
        abc.gcd(x, y);
    }
}

1. This Java program uses the Euclidean algorithm to calculate the greatest common divisor (GCD) of two input numbers.
2. The program defines a class called “Euclid” with a method called “gcd” that takes two long integers as parameters.
3. The method uses a while loop to calculate the GCD by repeatedly swapping the values of a and b and setting b to the remainder of a divided by b, until b is equal to 0.
4. The program then defines a static main method that creates an instance of the Euclid class and prompts the user to input two long integers.
5. The program reads the input using the Scanner class and passes the two integers to the gcd method.
6. Finally, the program prints the GCD.

Time Complexity: O(log min(a,b))
The time complexity of the program is O(log min(a,b)), where a and b are the two input numbers. This is because the Euclidean algorithm requires a maximum of log base 2 of the smaller of the two numbers iterations to compute the GCD.

Space Complexity: O(1)
The space complexity is O(1), which means that the amount of memory used by the program is constant and does not depend on the size of the input.

Testcase 1: The numbers entered by the user to calculate gcd in this case are 6 and 50.

$ javac Euclid.java
$ java Euclid
 
Enter any two numbers to calculate GCD
6 50
GCD is 2

Testcase 2: The numbers entered by the user to calculate gcd are 15 and 24.

$ javac Euclid.java
$ java Euclid
 
Enter any two numbers to calculate GCD
15 24
G.C.D is 3

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.