Program to Find the Greatest Common Divisor (GCD) in Java

Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCD of 36 and 60 is 12.

We will explore three different methods to find the GCD of two numbers using Java programming.

Method 1: Using Euclidean Algorithm

The Euclidean algorithm repeatedly replaces the larger number with its remainder when divided by the smaller number until the remainder becomes zero.

import java.util.Scanner;

public class Main {
    public static int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("GCD of " + num1 + " and " + num2 + " is " + findGCD(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12

Method 2: Using Recursion

In this method, we use recursion to apply the Euclidean algorithm.

import java.util.Scanner;

public class Main {
    public static int findGCD(int a, int b) {
        if (b == 0)
            return a;
        return findGCD(b, a % b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("GCD of " + num1 + " and " + num2 + " is " + findGCD(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12

Method 3: Using Iteration

In this method, we iterate from the smaller number down to 1 and find the largest number that divides both inputs.

import java.util.Scanner;

public class Main {
    public static int findGCD(int a, int b) {
        int gcd = 1;
        for (int i = 1; i <= Math.min(a, b); i++) {
            if (a % i == 0 && b % i == 0) {
                gcd = i;
            }
        }
        return gcd;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("GCD of " + num1 + " and " + num2 + " is " + findGCD(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12