# GCD of two numbers in Java

In this article, you will learn to find the greatest common divisor (G.C.D) or highest common factor (H.C.F) of numbers using different methods using Java programming.

Greatest common divisor (G.C.D) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers a, b, the greatest common divisor of a and b is denoted **gcd(a,b)**. These are different ways to find the GCD or HCF using Java -

## Using for loop

Here, we define a function to compute the G.C.D of two numbers x and y and return it. In each iteration, we check if our number perfectly divides both the given numbers. If this is true, we store the number as H.C.F. At the completion of the loop, we conclude with the largest number that perfectly divides both the numbers.

```
public class GetGCD
{
public static void main(String[] args)
{
// defining variables
int x = 4, y = 10, gcd = 1;
// iterate form 1 to the smallest of both numbers
for(int i = 1; i <= x && i <= y; i++)
{
if(x%i==0 && y%i==0)
gcd = i;
}
//prints the gcd
System.out.printf("GCD of %d and %d is: %d", x, y, gcd);
}
}
```

**Output of the above code:**

`GCD of 4 and 10 is: 2`

## Using while loop

In the given Java program, we have used the while loop to find the G.C.D of two numbers. In this method, smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding the larger integer. This process is continued until the condition x!=y becomes false.

```
public class FindGCD
{
public static void main(String[] args)
{
int x=32, y=28;
while(x!=y)
{
if(x>y)
x=x-y;
else
y=y-x;
}
System.out.printf("GCD of x and y is: " +y);
}
}
```

**Output of the above code:**

`GCD of x and y is: 4`

## Using user defined method

In the given program, we have defined a method named **findGCD()** to find the gcd of two numbers. It contains the logic to find the GCD of two numbers. We have parsed two parameters **x** and **y** of type int.

```
import java.util.Scanner;
public class ComputeGCD
{
//private static Scanner sc;
public static void main(String[] args)
{
// Initializing variables
int x, y, gcd = 0;
Scanner sc = new Scanner(System.in);
System.out.print("Please enter the first number: ");
x = sc.nextInt();
System.out.print("Please enter the second number: ");
y = sc.nextInt();
gcd = findGCD(x, y);
System.out.println("GCD of " + x + " and " + y + " = " + gcd);
}
public static int findGCD(int a, int b)
{
while(b != 0)
{
if(a > b)
{
a = a - b;
}
else
{
b = b - a;
}
}
return a;
}
}
```

**Output of the above code:**

```
Please enter the first number: 18
Please enter the second number: 20
GCD of 18 and 20 = 2
```

## Using Euclidean algorithm

The Euclidean algorithm is an efficient way to find the greatest common divisor of two numbers, the largest number that divides them both without a remainder.

```
import java.util.Scanner;
public class ComputeGCD
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Please enter the first number: ");
int x = sc.nextInt();
System.out.println("Please enter the second number: ");
int y = sc.nextInt();
System.out.println("GCD of " + x + " and " + y + " = " + findGCD(x,y));
}
static int findGCD(int x, int y)
{
int g=0, a, b;
// a is greater number
a = (x > y) ? x : y;
// b is smaller number
b = (x < y) ? x : y;
g = b;
while(a % b != 0)
{
g = a % b;
a = b;
b = g;
}
return g;
}
}
```

**Output of the above code:**

```
Please enter the first number: 15
Please enter the second number: 25
GCD of 15 and 25 = 5
```

### Related Articles

**Sort array in ascending order Java**

Automorphic number in Java

Pascal triangle program in Java

Factorial using recursion in java

Java random number between 1 and 10

Palindrome program in Java

Floyd triangle in Java

Pyramid pattern programs in Java

Star pattern programs in Java

Number pattern programs in Java

Java program to find area of rectangle

Matrix multiplication in Java

Electricity bill program in Java

Java program to find area of triangle

Area of circle program in Java

Remove duplicate elements from array in Java

Capitalize first letter of each word Java

Convert binary to decimal in Java

Convert decimal to binary in Java

Convert decimal to octal in Java

Convert decimal to hexadecimal in Java

Simple interest program in Java

Automorphic number in Java

Pascal triangle program in Java

Factorial using recursion in java

Java random number between 1 and 10

Palindrome program in Java

Floyd triangle in Java

Pyramid pattern programs in Java

Star pattern programs in Java

Number pattern programs in Java

Java program to find area of rectangle

Matrix multiplication in Java

Electricity bill program in Java

Java program to find area of triangle

Area of circle program in Java

Remove duplicate elements from array in Java

Capitalize first letter of each word Java

Convert binary to decimal in Java

Convert decimal to binary in Java

Convert decimal to octal in Java

Convert decimal to hexadecimal in Java

Simple interest program in Java