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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
package org.j2eedev.algorithmicpuzzles; public class EuclidAlgorithm { /** * @author Umashankar * @param args * {@link https://j2eedev.org} */ 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); } } |