Implementation of Euclidean Algorithm in Java

In this post, I am going to share the implementation of Euclidean Algorithm in Java.

Euclidean Algorithm is nothing but a method for calculating GCD of two numbers.

GCD (Greatest Common Divisor) : 

Take two numbers 20 and 30.

Factors of 20: 1, 2, 4, 5, 10, 20.

Factors of 30: 1, 2, 3, 5, 6, 10, 15, 30.

GCD refers to highest common factor of two numbers.

Now for 20 and 30, the common factor and the highest number is: 10. So GCD for 20 and 30 is 10.

The essence of this post is how can we calculate GCD in Java.

Well here it goes,

1:  import java.util.Scanner;  
2:  public class EuclideanAlgo {  
3:       public EuclideanAlgo() {  
4:       }  
5:       public static void main(String[] args) {  
6:            EuclideanAlgo euclideanAlgo = new EuclideanAlgo();  
7:            // Scanner class is used to values in the run time.  
8:            Scanner scanner = new Scanner(System.in);  
9:            // Below takes value of variable a.  
10:            System.out.println("Enter value for a: ");  
11:            int a = scanner.nextInt();  
12:            // Below takes value of variable b.  
13:            System.out.println("Enter value for a: ");  
14:            int b = scanner.nextInt();  
15:            // Calling method returnGCD to get GCD from there.  
16:            int gcd = euclideanAlgo.returnGCD(a, b);  
17:            System.out.println("GCD of " + a + " and " + b + " is: " + gcd);  
18:       }  
19:       private int returnGCD(int a, int b) {  
20:            if (b == 0)  
21:                 return a;  
22:            else {  
23:                 return returnGCD(b, a % b);  
24:            }  
25:       }  
26:  }  

Results are as follows:

In the above code, I used a Scanner class instance in lines 10 and 12 to record values of variables a and b at runtime and passed the values to a function in line 16.

The function returnGCD does the following:

Let's take value of a as 20 and b as 30.

Here 

The function is a recursive one and loops until it finds the second argument of the function to be 0.

If the second argument is not 0, it enters else and the arguments for the method becomes b and a%b.

Explantaion:

For example a is 20 and b is 30.

If condition is false since b is not 0.
Enters else and method is again called with arguments as 
a = 30 (b) and b = 20%30 (a%b) = 20.

If condition is false since b is not 0.
Enters else and method is again called with arguments as 
a = 20 (b) and b = 30%20 (a%b) = 10.

If condition is false since b is not 0.
Enters else and method is again called with arguments as 
a = 10 (b) and b = 20%10 (a%b) = 0.

Now this is a hit!

Code enters If and exits the method with value 10 which is GCD of 20 and 30.