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
Leave a Reply
You must be logged in to post a comment.