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