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

Output:

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

Output:

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

Output:

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

Output:

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

Output:

### 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

Output:

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