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:

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