Java Program to find GCD

February 6, 2021 11:10 pm IST

You are Here:

What is Greatest Common Divisor?

A largest number that exactly divides two or more integers.

In general, Greatest Common Divisor (GCD) is otherwise called as Greatest Common Factor (GCF) or Highest Common Factor (HCF)

Tips: It is recommended to use our online GCD calculator for better understanding.

Examples

The following table provides few examples of GCD of the given numbers.

Numbers	GCD
4, 10	2
6, 5	1
15, 30 , 45	15

GCD of Two Numbers

In the following example, we will find the GCD of the given two numbers (45, 90).

Example

Java Compiler

public class myClass { public static void main(String[] args) { int num1 = 45; int num2 = 90; int gcd = 1; int i; for(i=2; i<=num1 && i<=num2; i++) { // Checks if i is factor of both integers if((num1 % i == 0) && (num2 % i == 0)) gcd = i; } System.out.format("GCD of %d and %d: %d\n", num1, num2, gcd); } }

Output

GCD of 45 and 90: 45

GCD of any Two Given Numbers

In the following example, we will find the GCD of any two given numbers.

Example

Java Compiler

import java.util.Scanner; public class myClass { public static void main(String[] args) { Scanner reader = new Scanner(System.in); int num1, num2, i; System.out.print("Enter (int) num1 = "); num1 = reader.nextInt(); System.out.print("Enter (int) num2 = "); num2 = reader.nextInt(); int gcd = 1; for(i=2; i<=num1 && i<=num2; i++) { // Checks if i is factor of both integers if((num1 % i == 0) && (num2 % i == 0)) gcd = i; } System.out.format("\nGCD of %d and %d: %d\n", num1, num2, gcd); } }