Java Program to Find GCD of Two Numbers

Last Updated: 20 April, 2023

On this tutorial page we are going to learn how to write a Java program to find GCD of Two numbers.

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. There are different methods to find the GCD of two numbers, but the most common method is the Euclidean algorithm. Here are the steps to find the GCD of two numbers using the Euclidean algorithm:

Step 1: Let a and b be the two numbers for which we want to find the GCD.

Step 2: Divide the larger number by the smaller number, and write down the quotient and the remainder.

Step 3: If the remainder is 0, the GCD is the smaller number. If the remainder is not 0, replace the larger number with the smaller number, and replace the smaller number with the remainder. Repeat step 2 and 3 until the remainder is 0.

Step 4: The GCD is the last non-zero remainder obtained in step 3.

Following are examples of how to find the GCD (Greatest Common Divisor).

Example 1: Find GCD of Two Numbers using For Loop

  
  import java.util.Scanner;
  public class GCDofTwoNumbers1 {
    public static void main(String[] args) {
      int num1, num2, i, GCD = 0;
      Scanner sc = new Scanner(System.in);
      
      System.out.print("Enter the First Number: ");
      num1 = sc.nextInt();
      
      System.out.print("Enter the Second Number: ");
      num2 = sc.nextInt();
      sc.close();
      
      for (i = 1; i <= num1 && i <= num2; i++) {
        if (num1 % i == 0 && num2 % i == 0) {
          GCD = i;
        }
      }
      System.out.println("\nGCD of " + num1 + " and " + num2 + "  =  " + GCD);
    }
  }

Output

Enter the First Number: 240
Enter the Second Number: 150

GCD of 240 and 150  =  30

Example 2: Find GCD of Two Numbers using While Loop

  
  import java.util.Scanner;
  public class GCDofTwoNumbers2 {
    public static void main(String[] args) {
      int num1, num2, temp, GCD = 0;
      Scanner sc = new Scanner(System.in);
      
      System.out.print("Enter the First Number: ");
      num1 = sc.nextInt();
      
      System.out.print("Enter the Second Number: ");
      num2 = sc.nextInt();
      sc.close();
      
      while (num2 != 0) {
        temp = num2;
        num2 = num1 % num2;
        num1 = temp;
      }
      GCD = num1;
      System.out.println("\nGCD = " + GCD);
    }
  }

Output

Enter the First Number: 102
Enter the Second Number: 85

GCD = 17

Example 3: Find GCD of Two Numbers without temp Variable

  
  import java.util.Scanner;
  public class GCDofTwoNumbers3 {
    public static void main(String[] args) {
      int num1, num2, GCD = 0;
      Scanner sc = new Scanner(System.in);
      
      System.out.print("Enter the First Number: ");
      num1 = sc.nextInt();
      
      System.out.print("Enter the Second Number: ");
      num2 = sc.nextInt();
      sc.close();
      
      while (num2 != 0) {
        if (num1 > num2) {
          num1 = num1 - num2;
        } else {
          num2 = num2 - num1;
        }
      }
      
      GCD = num1;
      System.out.println("\nGCD  =  " + GCD);
    }
  }

Output

Enter the First Number: 175
Enter the Second Number: 60

GCD  =  5

Example 4: Find GCD of Two Numbers using Recursive Method

  import java.util.Scanner;
  public class GCDofTwoNumbers4 {
    public static void main(String[] args) {
      int num1, num2, GCD = 0;
      Scanner sc = new Scanner(System.in);
      
      System.out.print("Enter the First Number: ");
      num1 = sc.nextInt();
      
      System.out.print("Enter the Second Number: ");
      num2 = sc.nextInt();
      sc.close();
      
      GCD = findGCD(num1, num2);
      
      System.out.println("\nGCD of " + num1 + " and " + num2 + "  =  " + GCD);
    }
    
    public static int findGCD(int num1, int num2) {
      if (num2 == 0) {
        return num1;
      } else {
        return findGCD(num2, num1 % num2);
      }
    }
  }

Output

Enter the First Number: 70
Enter the Second Number: 120

GCD of 70 and 120  =  10