×

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).


Related Topics

Java Swings

Swing is a Java Foundation Class library and an extension to the Abstract Window Toolkit (AWT) (JFC).As compared to AWT, Swing has significantly better functionality, new components, increased component features,...

9 minutes read.

Java 9 Interface Private Method

Java 9 provides us the facility to include private methods inside the java interface. In java 8 and earlier versions, we are supposed to use only constant variables and abstract...

3 minutes read.

Add Time in Java

Before Java 8, java.util.Date was one of the most usually involved classes for addressing date-time values in java. Then Java 8 presented java.time.LocalDateTime and java.time.ZonedDateTime. Java 8 likewise permits us...

6 minutes read.

Java Math ceil() Method

The ceil() method of Math class returns the smallest double value which is closest to negative infinity and is greater than or equal to the argument. Syntax: public static double ceil(double a) Parameters: The...

2 minutes read.

Check whether a Number is a Power of 4 or Not in Java

There are many ways to figure out if an integer is a power of 4. This section will go over a variety of techniques for figuring out whether or not...

11 minutes read.

Various operations on the Queue using Stack in Java

The Java Collections Framework's core data structures are the Stack and Queue. They are used to store and retrieve identical data in a presentation sequence. These two linear data structures...

7 minutes read.

How to Read XML Files in Java?

Introduction Today, we are going to learn about how to read XML files in java. Before, reading the XML Files let us learn about XML. XML Files The full form of XML is...

8 minutes read.

Java AWT

Java AWT Java programming is used to develop different types of applications like window-based applications, web applications, Enterprise applications, or mobile applications. For creating standalone applications, Java AWT API is used....

11 minutes read.

How to Develop Programming Logic in Java?

Introduction In the world of software development, Java programming language is one of the most powerful programming languages that is used to create a wide range of applications. It includes desktop,...

18 minutes read.

Even Odd Program in Java

Even Odd Program in Java The number that are completely divisible by 2 are even and the number that leaves remainder are odd numbers. For example, the numbers 2, 0, 4,...

5 minutes read.

Sorting Program in Java

Sorting Program in Java: The sorting program in Java is used to sort arrays either in ascending or descending order.  There are two predefined methods available in Java that are...

6 minutes read.

Can we override Private Method in Java

In this article we will learn the concept of override, private method in java and we will now whether we can override private method in java or not. Override in Java Any...

3 minutes read.

Arrow Operator in Java

The introduction of arrow functions in ES6 gives you a more precise approach to define JavaScript functions. We can write shorter function syntax thanks to them. Your code will be...

4 minutes read.

Java Math.multiplyExact() method in Java

Java has an inbuilt math function called Math.multiplyExact() that returns the sum of the parameters. If the result exceeds an integer, an exception is thrown. There is no need to...

2 minutes read.

How to use scanner in Java

Scanner class in Java is the part of java.util package. Java programming language has various ways to read input from the user, Scanner class is one of the classes to...

5 minutes read.

Java Boolean toValue() Method

The valueOf() method of Java Boolean class returns a Boolean object representing the given Boolean or String value. It returns true, if the specified Boolean or string object is true...

2 minutes read.

For Loop Program in Java

For Loop Program in Java The for-loop program in Java is written when we want a particular set of statements to be executed repeatedly until the given criteria/ condition is met....

8 minutes read.

What are Array strings in Java?

In normal programming, An array is a group and a collection of identical forms of data that are stored in a sequential memory region and may be accessed using their...

4 minutes read.

flour pack problem in Java

Create a method called canPack and give it three int parameters: bigCount, smallCount, and objective. The bigCount option indicates the number of large flour bags (5 kilos each). The smallCount argument indicates...

3 minutes read.

Java Beans

It is a Java class, It follows conventions they are: It must have a no-arg constructorIt must be serializable.It must provide the methods to get and set the properties Uses Of Java...

3 minutes read.