GCD Program in Java
GCD Program in Java
The GCD program in Java outputs the GCD of the given numbers. In mathematics, Greatest Common Divisor (GCD), Greatest Common Factor or Highest Common Factor (HCF) of two numbers, x and y, is represented by GCD(x, y) or HCF(x, y).To find the GCD of number, first we need to find factors of that numbers. Let’s understand what is factors.
Factors: Factors are whole numbers that divide a given number completely. A number can have many factors. For example:
Factors of 21: 1, 3, 7, 21
Factors of 35: 1, 5, 7, 35 Now, to find out the GCD of 21 and 35, we must select the common factors of these two numbers and find the highest number from those common factors. We find that common factors of 21 and 35 are 1 and 7, but 7 is the highest among the two. Therefore, GCD(21, 35) = 7. Thus, GCD is the highest number that divides two or more than two given numbers completely.
There are different ways to find the GCD.
Using Java for Loop
Filename: GCDExample.java
public class GCDExample
{
public static void main(String argvs[])
{
int a = 78, b = 117; // Given numbers
int ans = 0; // contains GCD of the given numbers
// finding GCD
for(int i = 1; i <= a && i <= b; i++)
{
ans = ( a % i == 0 && b % i == 0 ) ? i : ans;
}
// Displaying results
if(a == 0) // Handling the scenario when any of the input numbers is zero
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + b);
else if(b == 0)
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + a);
else
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + ans);
}
}
Output:
The GCD of the numbers 78 and 117 is 39
Explanation: The GCD of any two numbers is always less than or equal smallest of the given numbers, which serve the condition of our for-loop. The for-loop runs from 1 to the minimum of the given numbers. In each iteration, we check whether the given numbers are divisible by the loop variable i or not. If the variable i divides both the numbers, we update the value of the ans variable else the variable ans remains the same.
Using Java while Loop
Filename: GCDExample1.java
public class GCDExample1
{
public static void main(String argvs[])
{
int a = 78, b = 117; // Given numbers
int temp1 = a, temp2 = b; // copy of the given numbers
// Handling the scenario when any of the input numbers is zero
if(a == 0)
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + b);
else if(b == 0)
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + a);
else
{
//finding GCD
while( temp1 != temp2 )
{
if(temp1 > temp2)
temp1 = temp1 - temp2;
else
temp2 = temp2 - temp1;
}
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + temp1);
}
}
}
Output:
The GCD of the numbers 78 and 117 is 39
Explanation: We are reducing the given numbers by subtracting the smaller number from the larger one and continue to do so until both the numbers are equal.
Using Java while Loop
Filename: GCDExample1.java
public class GCDExample1
{
public static void main(String argvs[])
{
int a = 78, b = 117; // Given numbers
int temp1 = a, temp2 = b; // copy of the given numbers
// Handling the scenario when any of the input numbers is zero
if(a == 0)
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + b);
else if(b == 0)
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + a);
else
{
//finding GCD
while( temp1 != temp2 )
{
if(temp1 > temp2)
temp1 = temp1 - temp2;
else
temp2 = temp2 - temp1;
}
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + temp1);
}
}
}
Output:
The GCD of the numbers 78 and 117 is 39
Explanation: We are reducing the given numbers by subtracting the smaller number from the larger one and continue to do so until both the numbers are equal.
Using Factors of the Given Numbers
Filename: GCDExample2.java
import java.util.List;
import java.util.ArrayList;
public class GCDExample2
{
public static void main(String argvs[])
{
int a = 78, b = 117; // Given numbers
int ans = 0; // contains the GCD of the given numbers
// List for storing factors
List<Integer> al1 = new ArrayList<Integer>();
List<Integer> al2 = new ArrayList<Integer>();
// Finding factors of the given numbers
for(int i = 1; i <= a; i++)
{
if(a % i == 0)
{
al1.add(i); // adding factors to the list
}
}
for(int i = 1; i <= b; i++)
{
if(b % i == 0)
{
al2.add(i); // adding factors to the list
}
}
// Converting the lists into Integer arrays.
Integer[] f1 = new Integer[al1.size()];
f1 = al1.toArray(f1);
Integer[] f2 = new Integer[al2.size()];
f2 = al2.toArray(f2);
// Two pointer approach to find the highest factor
for(int i = 0, j = 0; i < f1.length && j < f2.length;)
{
// Common element found
if(f1[i] == f2[j])
{
ans = f1[i]; // updating our result
i++;
j++;
}
else if(f1[i] < f2[j])
{
i++;
}
else
{
j++;
}
}
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + ans);
}
}
Output:
The GCD of the numbers 78 and 117 is 39
Explanation: In the above approach, we are finding all the factors of the given numbers and storing those factors in the lists. Then we are converting those lists into integer arrays. The first integer array contains all the factors of the first input number, and the second integer array contains the factors of the second input number. Since we have found the factors from one to the number itself, therefore, the integer arrays contain all the factors in ascending order. Now, we have applied the two-pointer approach to find the common elements, as the arrays are sorted. The highest common element is our answer that we are displaying on the console.
Using Euclid’s Algorithm
Euclid’s algorithm is the best approach to find the GCD as it takes less time as compared to other approaches. The algorithm says:
- If a1 = 0, then GCD(a1, a2) = a2
- Else If a2 = 0, then GCD(a1, a2) = a2
- Else If a1 != 0 and a2 != 0, then GCD(a1, a2) = GCD(a2, a1 % a2)
The following program implements the above algorithm to find the GCD of given numbers.
Filename: GCDExample3.java
public class GCDExample3
{
//Method implementing Euclid's algorithm
public static int findGCD(int n1, int n2)
{
// base cases
if(n1 == 0) return n2;
if(n2 == 0) return n1;
// recursively finding the GCD
return findGCD(n2, n1 % n2);
}
public static void main(String argvs[])
{
int a = 78, b = 117; // Given numbers
int temp1 = a, temp2 = b; // copy of the given numbers
int ans = findGCD(a, b); // invoking the method and storing the result.
System.out.println("The GCD of the numbers " + a + " and " + b + " is " + ans);
}
}
Output:
The GCD of the numbers 78 and 117 is 39
Finding GCD of more than two numbers
So far, we have only discussed the GCD of the two given numbers. However, it is also possible to find the GCD of more than two numbers. The following program illustrates the same.
Filename: GCDExample4.java
public class GCDExample4
{
//Method implementing Euclid's algorithm
public static int findGCD(int n1, int n2)
{
// base cases
if(n1 == 0) return n2;
if(n2 == 0) return n1;
// recursively finding the GCD
return findGCD(n2, n1 % n2);
}
public static void main(String argvs[])
{
// input array
int arr[] = {6, 10, 16, 28, 78, 90, 112, 188, 200, 290, 310, 444};
int size = arr.length; // Calculating size of the input array
int ans = 0; // contains the GCD of the entire array
for(int i = 0; i < size; i++)
{
// invoking method and updating the result
ans = findGCD(ans, arr[i]);
}
System.out.println("The GCD of the given numbers is " + ans);
}
}
Output:
The GCD of the given numbers is 2
Explanation: We are iterating over every element of the input array and recursively calculating GCD using Euclid’s algorithm.
Note: In all the above examples, we have discussed about the non-negative elements. However, GCD of negative numbers do exist. In fact, the GCD is independent of the sign of the input numbers, i.e., GCD(-a, -b) = GCD(-a, b) = GCD(a, -b) = GCD(a, b).