# Euclid Algorithm

The Euclid Algorithm is used to find the GCD (Greatest Common Divisor) of two numbers i.e. the largest number the divides both the numbers. For instance,
35= 3 x 5
10= 2 x 5
GCD = multiplication of common factors
= 5

60= 2 x 2 x 3 x 5
36= 2 x 2 x 3 x 3
GCD = multiplication of common factors
= 2 x 2 x 3
= 12

So here’s how the Logic works:

1. In order to find the GCD of two numbers we have to divide one number by the second and take note of the reminder. For example. a=36, b=60. So on dividing we get the reminder as 24
2. Assign a=remainder (i.e. b%a) and b=a
3. Repeat the process (i.e. recursively call GCD function) till the remainder is zero.

Code:

``````
public class Euclid {

public static int gcd(int a, int b){
if(a==0)
return b;

return gcd(b%a, a);

}

public static void main (String [] args){
int a=61, b=2;
System.out.println(gcd(a,b));
}
}
``````

HAPPY LEARNING!!

Algorithms, Coding Challenge, Technology

This site uses Akismet to reduce spam. Learn how your comment data is processed.