Java Program to Find the GCD of Two Numbers

The GCD (Greatest Common Divisor) of two numbers, also called the HCF (Highest Common Factor), is the largest number that divides both of them with no remainder. For example, the divisors of 12 are 1, 2, 3, 4, 6, 12 and the divisors of 18 are 1, 2, 3, 6, 9, 18, so GCD(12, 18) = 6.

1. How the Euclidean Algorithm Works

The Euclidean algorithm is the fastest way to find a GCD by hand or in code. It is based on the fact that GCD(a, b) = GCD(b, a % b):

1. Divide a by b and take the remainder r.
2. Replace a with b and b with r.
3. Repeat until b is 0. The value left in a is the GCD.

For 240 and 150: 240 % 150 = 90, 150 % 90 = 60, 90 % 60 = 30, 60 % 30 = 0, so the GCD is 30.

2. GCD Using a for Loop

The simplest method tries every number from 1 up to the smaller of the two and remembers the last one that divides both.

public class GcdLoop {
    public static void main(String[] args) {
        int a = 240, b = 150;
        int gcd = 1;

        for (int i = 1; i <= Math.min(a, b); i++) {
            if (a % i == 0 && b % i == 0) {
                gcd = i;
            }
        }

        System.out.println("GCD of " + a + " and " + b + " = " + gcd);
    }
}

GCD of 240 and 150 = 30

3. GCD Using the Euclidean Algorithm and User Input

The while loop applies the Euclidean steps until the remainder is 0. It needs far fewer steps than the for loop above.

import java.util.Scanner;

public class GcdEuclid {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the first number: ");
        int a = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int b = scanner.nextInt();
        scanner.close();

        int x = a, y = b;
        while (y != 0) {
            int remainder = x % y;
            x = y;
            y = remainder;
        }

        System.out.println("GCD of " + a + " and " + b + " = " + x);
    }
}

Enter the first number: 102
Enter the second number: 85
GCD of 102 and 85 = 17

4. GCD Using Recursion

The rule GCD(a, b) = GCD(b, a % b) can be written as a one-line recursive method, with GCD(a, 0) = a as the base case.

public class GcdRecursion {

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println("GCD of 175 and 60 = " + gcd(175, 60));
        System.out.println("GCD of 48 and 36 = " + gcd(48, 36));
        System.out.println("GCD of 17 and 5 = " + gcd(17, 5));
    }
}

GCD of 175 and 60 = 5
GCD of 48 and 36 = 12
GCD of 17 and 5 = 1

5. GCD Using BigInteger.gcd()

Java's BigInteger class has a built-in gcd() method that works for numbers of any size.

import java.math.BigInteger;

public class GcdBigInteger {
    public static void main(String[] args) {
        BigInteger a = new BigInteger("600000000000000000000");
        BigInteger b = new BigInteger("450000000000000000000");

        System.out.println("GCD = " + a.gcd(b));
    }
}

GCD = 150000000000000000000

6. Summary

• The GCD (or HCF) is the largest number that divides both numbers exactly.
• Checking every number up to the smaller value works but is slow for large inputs.
• The Euclidean algorithm repeats (a, b) = (b, a % b) until b is 0.
• BigInteger.gcd() handles numbers of any size.

Related Programs

• Java Program to Find the LCM of Two Numbers
• Java Program to Check Whether a Number is Prime
• Java Program to Find the Quotient and Remainder
• All Java Programs for Beginners