Finding Greatest Common Divisor (GCD of two numbers) is a simple mathematical problem, the algorithm (Euclid’s Algorithm) for which was devised over 2300 years ago. It is often a common interview question, not tricky though, is asked just to check one of the Algorithmic Design Technique , Recursion as the algorithm can be implemented with Recursion.

## Euclid’s Algorithm

To compute greatest common divisor of two non negative integers “p” and “q”.

- if q is 0, the answer is p
- if not , divide “p” by “q” and take the remainder “r”. The answer is the greatest common divisor of “q” and “r”
- The high-lighted one above is a sub problem of GCD. Carry same steps as above for sub problem, until it is devised to step 1.

## Euclid’s Algorithm implementation in Java

Here is the implementation for Euclid’s Algorithm for finding GCD of two numbers.

package com.jminded.algorithmicpuzzles; public class EuclidAlgorithm { /** * @author Umashankar * @param args * {@link https://jminded.com} */ public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(gcd(16, 32)); System.out.println(gcd(3, 66)); } /** * GCD of given two numbers * @param p * @param q * @return */ public static int gcd(int p, int q){ if(q==0) return p; int r=p%q; return gcd(q,r); } }