## ðŸŽ¯ Overview

Write a Java program to find the Greatest Common Divisor(GCD) of two numbers.

Important concepts to be aware of:

- This problem can be solved using Euclidean algorithm by subtraction. This algo says that GCD of two numbers = GCD of difference of the two and the smaller number.
- This problem can also be solved if we keep dividing the bigger number by smaller number, until the remainder is zero. This is a better approach to solve this problem.

I have solved using both approaches below.

## ðŸŽ¯ Solving the problem in Java

```
/**
* Problem 9: Write a Java program to find the Greatest Common Divisor(GCD) of two numbers.
*/
public class Problem_9 {
public static void main(String[] args) {
System.out.println("Enter the first number:");
Scanner sc = new Scanner(System.in);
int firstNumber = sc.nextInt();
System.out.println("Enter the second number:");
int secondNumber = sc.nextInt();
System.out.println("GCD is: " + calculateGCD(firstNumber, secondNumber));
System.out.println("GCD is: " + calculateGCDBetterWay(firstNumber, secondNumber));
}
// Also known as Euclidean algorithm by subtraction.
// This algo says that GCD of two numbers = GCD of difference of the two and the smaller number.
private static int calculateGCD(int firstNumber, int secondNumber) {
if (firstNumber == 0) {
return secondNumber;
} else if (secondNumber == 0) {
return firstNumber;
} else if (firstNumber == secondNumber) {
return firstNumber;
}
if (firstNumber > secondNumber) {
return calculateGCD(firstNumber - secondNumber, secondNumber);
} else {
return calculateGCD(secondNumber - firstNumber, firstNumber);
}
}
// Keep dividing the bigger number by smaller number, until the remainder is zero.
private static int calculateGCDBetterWay(int firstNumber, int secondNumber) {
if(firstNumber == 0) {
return secondNumber;
}
return calculateGCDBetterWay(secondNumber % firstNumber, firstNumber);
}
}
```

**Output**:

```
Enter the first number:
23
Enter the second number:
21
GCD is: 1
GCD is: 1
Process finished with exit code 0
```

## ðŸŽ¯ Github

Code shared in this post can be found here.