Program to calculate GCD of Two Numbers in Java

August 20, 2021

Program to calculate GCD of Two Numbers 

In this article, we will discuss about GCD of Two Numbers in Java. GCD of Two Numbers or integers (where integers not equal to zero) is largest positive integer that divides each of the integers. For example, GCD of  12 and 16 is 4 , where factors of 12==>1,2,4,6,12
factors of 16==>1,2,4,8,16
common factors are 1,2,4
greatest common factor is 4.

Program to check a number is prime or not in C++

Algorithm for GCD of Two Numbers:

  • Take Two Numbers num1 and num2 as input.
  • Initialize a variable i to minimum of num1 and num2 and loop until i is greater than or equal to 1.
  • Check if i divides num1 and num2 completely or not. If divides completely then break the loop.
  • Now , print the value of i.

Code for GCD of Two Numbers in Java

import java.util.*;
public class Solution
{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int num1=sc.nextInt();
		int num2=sc.nextInt();
		int min=num1<num2?num1:num2,i;
		for(i=min;i>=1;i--)
		    if((num1%i==0) && (num2%i==0))
		        break;
		System.out.println("GCD of "+num1+" and "+num2+" is "+i);
	}
}

Output : 

12
30
GCD of 12 and 30 is 6

Euclidean Algorithm :

Basic Euclidean Algorithm for GCD 
The algorithm is based on the below facts. 

  • If we subtract a smaller number from a larger (we reduce a larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
  • Now instead of subtraction, if we divide the smaller number, the algorithm stops when we find remainder 0.

Code in Java (Efficient Approach)

import java.util.*;
public class Solution 
{
    public static int gcd(int num1, int num2) 
    {
        if (num2 == 0)
            return num1;
    
        return gcd (num2, num1 % num2);
    }

    public static void main (String[]args)
    {
        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();

        System.out.println("GCD of "+num1+" and "+num2+" is "+gcd(num1,num2));
    }
}

Output : 

12
30
GCD of 12 and 30 is 6