Site icon

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

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 
Exit mobile version