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:

- 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
- Assign a=remainder (i.e. b%a) and b=a
- Repeat the process (i.e. recursively call GCD function) till the remainder is zero.

Code:

View on/ Download from Github: (LINK)

```
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!!