Euclid’s Algorithm for finding GCD of two numbers

by

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”.

  1. if q is 0, the answer is p
  2. if not , divide “p”  by “q” and take the remainder “r”. The answer is the greatest common divisor of “q” and “r”
  3. 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);
	}
}

Leave a Comment