# Euclid’s Algorithm for finding GCD of two numbers

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
*/
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);
}
}```