Java Code to find Greatest Common Divisor (GCD) using recursion / loop

Greatest Common Divisor (GCD) or Greatest Common Factor (GCF), is the largest positive integer which divides both numbers.

For example, consider 12, 54
Divisiors of 54 are 1, 2 , 3, 6, 9 , 18, 27 , 54
Divisiors of 12 are 1, 2 , 3, 6, 12
Now the common divisors of two numbers are 1,2,3,6. Now biggest (Greatest) number is is 6.

So GCD(12,54) is 6.

The following code illustrates how to find Greatest Common Divisior (GCD) of two numbers which are passed through command line. We can find GCD in several ways. In our code, we have written two functions to find GCD. One is using loop and another is using recursion.

Now let us  calculate GCD using loop for the input (12 & 54)

logic
loop
c = a%b;

if(c==0) return b;

a = b; b = c;
loop end

1) 12%54 = 12
2) now a=54, b=12
3) 54%12=6
4) now a=12, b=6
5) 12%6= 0
6) now b is 6 which is GCD

Java Program to calculate Greatest Common Divisior (GCD) using loop and recursion. 

package com.javaonline;

class GCD {
  public static void main(String[] args) {

if (args.length!=2)
{
	System.out.println("invalid input");
	System.exit(0);

}

int a=0;
int b=0;

try
{
	a=Integer.parseInt(args[0]);
	b=Integer.parseInt(args[1]);
}
catch (Exception e)
{
	System.out.println("Input Error . input format ->  java GCD number1 number2 . eg. java GCD 24 54 ");
	System.exit(0);
}

	int gcd=GCD(a,b);

	System.out.println("Using Loop GCD("+ a + "," + b + ")  "  +"is "  + gcd);

	int gcdR=GCDUsingRecursion(a,b);

	System.out.println("Using Recursion GCD("+ a + "," + b + ")  "  +"is "  + gcdR);
  }

// Finding GCD using Loop

public static int GCD(int a,int b)
  {
    int c;
    while(true)
    {
	   c = a%b;
	   if(c==0)  return b;
	   	a = b;
	   	b = c;
    }
  }

// Finding GCD using Recursion

public static int GCDUsingRecursion(int a, int b) {

   if (b==0)    return a;
   else
	   return GCDUsingRecursion(b, a % b);
 }

}

Running the above program will result the following ….

1) D:\javaonline>java GCD 54 24
Using Loop GCD(54,24) is 6
Using Recursion GCD(54,24) is 6

2) D:\javaonline>java GCD 100 500
Using Loop GCD(100,500) is 100
Using Recursion GCD(100,500) is 100