GCD of two numbers Euclidean algorithm in java (iterative/ recursive)

• The greatest common divisor (GCD) is the largest natural number that divides two numbers without leaving a remainder.
  • e.g gcd ( 10,15) = 5 or gcd ( 12, 18) = 18
• The Euclidean algorithm is the efficient algorithm to find GCD of two natural numbers.
  • Algorithm is named after famous greek mathematician Euclid.
• GCD is also referred as highest common factor (HCF) or greatest common factor (GCF) or  greatest common measure (GCM).
• The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

We will calculate GCD of two natural numbers using recursive & iterative algorithm. We have shown couple of methods (recursive & iterative version of each method) to find GCD of two numbers.

Program: find GCD or HCF of two natural numbers in java (recursive/iterative)

package org.learn;

import java.util.Scanner;

public class GCDOfNumbers {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			
			System.out.printf("1. Enter first number : ");
			int a = scanner.nextInt();
			
			System.out.printf("2. Enter second number : ");
			int b = scanner.nextInt();
			
			int gcd =  gcdIterativeMethod1(a, b);
			System.out.printf("3. gcdIterativeMethod1(%d,%d) = %d \n",a,b,gcd);			
			
			gcd =  gcdRecursiveMethod1(a, b);
			System.out.printf("4. gcdRecursiveMethod1(%d,%d) = %d \n",a,b,gcd);
			
			gcd =  gcdIterativeMethod2(a, b);
			System.out.printf("5. gcdIterativeMethod2(%d,%d) = %d \n",a,b,gcd);
			
			gcd =  gcdRecursiveMethod2(a, b);
			System.out.printf("6. gcdRecursiveMethod2(%d,%d) = %d ",a,b,gcd);
		}
	}

	private static int gcdIterativeMethod1(int a, int b) {
		int temp = 0;
		while (b != 0) {
			temp = b;
			b = a % b;
			a = temp;
		}
		return a;
	}
	
	private static int gcdRecursiveMethod1(int a, int b) {
		if (b == 0)
			return a;

		return gcdRecursiveMethod1(b, a % b);
	}
	
	private static int gcdIterativeMethod2(int a, int b) {
		while (a != b)
			if (a > b)
				a -= b;
			else
				b -= a;
		return a;
	}
	
	private static int gcdRecursiveMethod2(int a, int b) {
		if (a == b)
			return a;

		if (a > b)
			return gcdRecursiveMethod2(a -= b, b);
		else
			return gcdRecursiveMethod2(a , b-=a);
	}
}

Output: find GCD or HCF of two natural numbers in java (examples)

1. Enter first number : 12
2. Enter second number : 18
3. gcdIterativeMethod1(12,18) = 6 
4. gcdRecursiveMethod1(12,18) = 6 
5. gcdIterativeMethod2(12,18) = 6 
6. gcdRecursiveMethod2(12,18) = 6 

1. Enter first number : 10
2. Enter second number : 15
3. gcdIterativeMethod1(10,15) = 5 
4. gcdRecursiveMethod1(10,15) = 5 
5. gcdIterativeMethod2(10,15) = 5 
6. gcdRecursiveMethod2(10,15) = 5