Program to calculate GCD of Three Numbers in Java

August 20, 2021

Program to calculate GCD of three numbers

In this article we will discuss about GCD of three numbers. GCD of three integers (where integers not equal to zero) is largest positive integer that divides each of the three integers. For example GCD of 12 , 16 , 22 is 2 where factors of 12==>1,2,3,4,6,12
factors of 16==>1,2,4,8,16
factors of 22==>1,2,11,22
common factors==>1,2
greatest common factor==>2

GCD of three numbers in java

Algorithm for GCD of three numbers:

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

Code for GCD of three 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 num3=sc.nextInt();
		int min=Math.min(num1,Math.min(num2,num3));
                int i;
		for(i=min;i>=1;i--)
		    if((num1%i==0) && (num2%i==0) && (num3%i==0))
		        break;
		System.out.println("GCD of "+num1+", "+num2+" and "+num3+" is "+i);
	}
}

Output : 

12
16
22
GCD of 12, 16 and 22 is 2

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();
        int num3= sc.nextInt();	
        System.out.println("GCD of "+num1+", "+num2+" and num3"+" is "+gcd(num1,gcd(num2,num3)));
    }
}

Output : 

12
16
22
GCD of 12, 16 and 22 is 2