Greatest Common Divisor (GCD) of Two Numbers Java Program

In this post we'll see how to write a Java program to calculate the greatest common divisor (GCD) of two numbers. It is also known as the highest common factor (HCF).

GCD of two integers is the highest integer that can completely divide both the integers which means remainder is 0 for both of the integers. For example- GCD of 33 and 110 is 11 as that is the highest number which completely divides both numbers.

33 = [1, 3, 11]
110 = [1, 2, 5, 10, 11]

Java program to calculate GCD of two numbers can be written using following approaches-

Writing the logic as per the explanation of calculating GCD. Find the highest number that completely divided both numbers by doing that in a loop.
Using Euclid algorithm (Repeated subtraction logic)
Using Euclid algorithm (Repeated division logic)

1. Finding highest common divisor using loop

In this approach you need to run the loop from 1 up to minimum of two numbers and keep dividing both the numbers with the current loop iteration value. If it completely divides both the numbers then store it. By the end of the loop you will have the GCD.

import java.util.Scanner;
public class GCDCompute {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    System.out.println("Enter first number");
    int a = sc.nextInt();
    
    System.out.println("Enter second number");
    int b = sc.nextInt();

    System.out.println(computeGCD(a, b));      
  }
  
  public static int computeGCD(int a, int b) {
    // edge case where one or both numbers are zero
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }
    int gcd = 1;
    for(int i = 1; i <= a && i <= b; i++) {
      if(a%i == 0 && b%i==0) {
        // completely divides so store the i value
        gcd = i;
      }
    }
    return gcd;
  }
}

Output

Enter first number
112
Enter second number
30
GCD is 2
Enter first number
0
Enter second number
5
GCD is 5

2. Using Euclid algorithm (Repeated subtraction logic) - Java Program

Euclid algorithm is considered more efficient than the general approach shown above. The repeated subtraction variant of Euclid algorithm states that the GCD of two numbers remains same if the greatest of the two numbers is replaced by the difference of the two numbers. This process is repeatedly done until both of the numbers become equal. This number at the end is the GCD of the two given numbers.

For example, if the numbers are 36 and 16.

Greater of the two is 36 so that is replaced by the difference of the two.
So, now the numbers are 20 and 16 again process is repeated
Numbers are now 16 and 4; again subtract 4 from 16 giving 12
Numbers 12 and 4 give 8 and 4
8 and 4 give 4 and 4, since numbers are equal now so 4 is the GCD.

public class GCDCompute {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter first number");
    int a = sc.nextInt();
    
    System.out.println("Enter second number");
    int b = sc.nextInt();

    System.out.println("GCD is " + gcdEuclidSubtraction (a, b));
  }
  
  public static int gcdEuclidSubtraction(int a, int b) {
    // edge case where one or both numbers are zero
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }
    while(a != b) {
      if(a > b) {
        a = a - b;
      }else {
        b = b - a;
      }
    }
    
    return a;
  }
}

Output

Enter first number
36
Enter second number
16
GCD is 4

3. Using Euclid algorithm (Repeated division logic) - Java Program

This variant of Euclid algorithm further optimizes it by using division rather than subtraction. It works as follows.

Divide the greater of the two number by the second number.
Assign second number to the first number and remainder to the second number.
Repeat step 1 and 2 until the remainder is zero. The last non-zero remainder is the GCD.

For example, if the two numbers are 36 and 16 then-

Divide 36 by 16 giving remainder as 4.
Now 16 becomes the first number and 4 becomes the second number. Repeat the process of division giving remainder as 0.
That last non-zero remainder 4 is the GCD.

public class GCDCompute {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter first number");
    int a = sc.nextInt();
    
    System.out.println("Enter second number");
    int b = sc.nextInt();

    System.out.println("GCD is " + gcdEuclidDivision(a, b));    
  }
  public static int gcdEuclidDivision(int a, int b) {
    int temp;
    // Find the maximum of two numbers, which is assigned to variable a
    if(a < b) {      
      temp = a;
      a = b;
      b = temp;
    }
    while(b != 0) {
      temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }
}

Output

Enter first number
440
Enter second number
550
GCD is 110
Enter first number
17
Enter second number
37
GCD is 1

That's all for this topic Greatest Common Divisor (GCD) of Two Numbers Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Monday, September 22, 2025