Euclid's Algorithm to find Greatest Common Divisor

Objective: Given 2 number m and n, we have to find Greatest Common Divisor.

Approach: Euclid's Algorithm to find Greatest common Divisor. Suppose m and n is two integer, m > n. 
1. Get reminder while divide m by n, if it 0 then we have our answer n as GCD.
2. If reminder is not 0, then divide m by n and then get reminder. Thereafter, set reminder to n = r; m = n; and repeat step 1 to get GCD of 'm' and 'n'.

Solution: Java Code

	public class EuclidAlgo {
	public static void main(String ...arg) {
	Scanner scanner = new Scanner(System.in);
	int m = scanner.nextInt();
	int n = scanner.nextInt();
	System.out.println("GCD: "+ gcd(m, n));
	}
	private static int gcd(int m, int n) {
	int r = m % n;
	int q = m / n;
	if(r == 0) return n;
	return gcd(n, r);
	}
	}

view raw EuclidAlgo.java hosted with ❤ by GitHub