Java Program to Find GCD of two Numbers

May 25, 2023

What are GCD?

In this Article, we will write a program to find GCD of two numbers in Java.
GCD stands for Greatest Common Divisor, also known as Highest Common Factor (HCF). It is the largest positive integer that divides two or more integers without leaving a remainder.

Program to Find GCD of Two Numbers Using For Loop:

Run

import java.util.*;

public class Main{
  public static void main(String[] args) {
    // Taking input of two numbers
    Scanner scn = new Scanner(System.in);
    int num1 = scn.nextInt();
    int num2 = scn.nextInt();
    
    // int n1 = 81, n2 = 153;
    
    // initializing answer variable
    int gcd = 1;

    for (int i = 1; i <= num1 && i <= num2; i++){
        if (num1 % i == 0 && num2 % i == 0)
            gcd = i;
    }
    System.out.println("GCD of " + num1 +" and " + num2 + " is " + gcd);
  }
}

Output:

GCD of 81 and 153 is 9

Explanation: In the above program, the user enters two numbers and we initialize a variable gcd to 1, which will store the GCD of the two numbers. In the for loop that starts from 1 and goes up to the smaller of the two numbers. For each iteration of the loop, we check whether the current value of i is a factor of both num1 and num2. If i is a factor of both num1 and num2, the program updates the value of gcd to i. and after the loop has finished running, the program outputs the GCD of the two numbers.

Program to Find GCD of Two Numbers Using while Loop:

Run

import java.util.*;

public class Main{
  public static void main(String[] args) {
    // Taking input of two numbers
    Scanner scn = new Scanner(System.in);
    int num1 = scn.nextInt();
    int num2 = scn.nextInt();
    
    int temp1 = num1;
    int temp2 = num2;
    // loop to calculate GCD of two numbers
    while(num1 != num2) {
      if(num1 > num2) {
        num1 -= num2;
      }
      else {
        num2 -= num1;
      }
    }
    System.out.println("GCD of " + temp1 +" and " + temp2 + " is " + num1);
  }
}

Output:

GCD of 81 and 153 is 9

Explanation: In the above program, the user enters two numbers. The program enters a while loop that runs as long as the first number is not equal to the Second number. For each iteration of the loop, the program checks whether the current value of the First number is greater or less than the second number. After the loop has finished running, the program outputs the GCD of the two numbers as the first number i.e. num1.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others