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 the Java programming language.
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.
GCD of two numbers in 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
GCD of two numbers in Java 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
GCD of two numbers in Java using user defined method
In the given Java 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
GCD of two numbers in Java 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 JavaAutomorphic 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