GCD of Two Numbers in Java

The Greatest Common Divisor (GCD) is an important concept in mathematics and computer science, which represents the largest number that can divide two or more numbers without leaving a remainder. GCD plays a vital role in simplifying fractions, optimizing algorithms, and solving problems in fields like cryptography and data processing. In Java, there are several ways to calculate the GCD, from basic loop-based methods to advanced algorithms like the Euclidean method. In this article, we will learn how to find the GCD of two numbers.

Table of Contents:

• What is the GCD of Two Numbers?
• Method 1: GCD of Two Numbers Using a Loop
• Method 2: Find the GCD of Two Numbers by the Euclidean Algorithm
• Method 3: GCD of Two Numbers Using Built-in Method
• Method 4: GCD of Two Numbers Using Recursion
• Method 5: GCD of Both Positive and Negative Numbers
• Stein’s Algorithm to Find the GCD of Two Numbers
• Time and Space Complexity
• Real-Life Applications of GCD
• Conclusion

What is the GCD of Two Numbers?

GCD or Greatest Common Divisor is also known as HCF (Highest Common Factor), and is defined as the largest positive integer that exactly divides two or more given integers without leaving a remainder. In simple words, it is referred to as the biggest number that has a common factor in it.

For example, let us find the GCD of 24 and 18.

• Factors of 24: 1, 2, 3, 4, 6, 12, 24
• Factors of 18: 1, 2, 3, 6, 9, 18

The common factors of 24 and 18 are: 1, 2, 3, 6; hence, the GCD of 24 and 18 is 6.

Master Java Today - Accelerate Your Future

Enroll Now and Transform Your Future

Explore Program

Properties of GCD

Below are the properties of GCD.

1. GCD of any number and 0: If one number is 0, the other number is any other number; the GCD will be 0, as any number that divides 0 gives the result as 0.
2. Commutative Property: According to the commutative property, the order of the numbers doesn’t matter, i.e., (a,b)=(b,a), which means that swapping the numbers will give the GCD, as the divisibility of the numbers is not dependent on the order of the numbers. For example, GCD(24,18)=6 and GCD(18,24)=6.
3. Associative Property: According to the associative property, the way numbers are grouped in addition or multiplication does not change the result, i.e., (a+b)+c=a+(b+c). For example, GCD(a, GCD(b, c)) = GCD(GCD(a, b), c).
4. If a divides b, then GCD(a,b) = a: If b is a multiple of a, then a is automatically the largest common divisor. For example, GCD(5,20)=5.

Now, let us discuss the different methods for finding the GCD of two numbers.

Method 1: GCD of Two Numbers Using a Loop

In this method, we will discuss how to find the greatest common divisor (gcd) of two numbers using a for loop and a while loop.

1. GCD of Two Numbers Using a for Loop

In this method, we check all the numbers from 1 to the smaller number among the two numbers. We find the GCD, and find the largest number that divides both of the numbers without leaving a remainder. This method is simple but less efficient.

Code:

Output:

Explanation: In the above Java program, the numbers are assigned as 12 and 18, and the GCD is initialized as 1. The for loop starts from 1 to the minimum of the two numbers. If a variable divides both the numbers, gcd is updated and printed.

2. Find the GCD of Two Numbers Using While

In this method, we are using the same approach as above, but instead of using a for-loop, we are using a while loop here.

Code:

Output:

Explanation: In the above Java program, the numbers are assigned as 12 and 18, and the gcd is initialized as 1. The while loop starts from 1 and goes till i is less than or equal to the minimum of the two numbers. If a variable divides both the numbers, gcd is updated and printed.

Method 2: Find the GCD of Two Numbers by the Euclidean Algorithm

The Euclidean Algorithm is one of the oldest methods to find the GCD or HCF of two positive numbers, which was created by the ancient Greek mathematician Euclid around 300 BC. Despite it being 2000 years old, it is still used today because of its simplicity and efficiency. In this method, we will learn how to find the GCD of two numbers by using the Euclidean algorithm.

1. Euclidean Algorithm Using Subtraction

In this method, the smaller number is subtracted from the largest number until both numbers become equal, and the resulting final equal value is the GCD.

Pseudo-code:

SET a = first number
SET b = second number
WHILE a != b
    IF a > b THEN
        a = a - b
    ELSE
        b = b - a
    ENDIF
END WHILE
PRINT a // or b, both will be the GCD

Code:

Output:

Explanation: In the above Java program, we are using the Euclidean subtraction algorithm to find the GCD. In this method, we repeatedly subtract the smaller number from the larger number until both numbers become equal. The final value, when both numbers are equal, is the GCD of the two numbers.

2. Euclidean Algorithm Using Division

By using division in the Euclidean Algorithm, we use the modulus operator (%) to find the GCD, which reduces the number of steps as compared to the subtraction method. For example, in the image below, the two numbers 78 and 66 are used to find the GCD. Number 66 is smaller than 78, hence operation 78%66 is performed, which gives the remainder as 12. Then the operation 66%12 is performed as below. This process is repeated until the remainder found is 0.

Pseudo-code:

SET a = first number
SET b = second number
WHILE b != 0
    remainder = a % b
    a = b
    b = remainder
END WHILE
PRINT a // GCD

Code:

Output:

Explanation: In the above Java program, the numbers 78 and 66 are divided until their remainder is found as 0.

Method 3: GCD of Two Numbers Using Built-in Method

In Java, GCD can be calculated using the built-in method gcd() method from the java.math.BigInteger class. This method uses the Euclidean Algorithm internally to find the greatest common divisor between two numbers, and can handle large integers that exceed the limits of primitive data types like int or long. To use this method, the numbers have to be first converted into BigInteger objects.

Code:

Output:

Explanation: In the above Java program, the built-in method .gcd() is used to find the greatest common divisor of the two numbers.

Method 4: GCD of Two Numbers Using Recursion

Recursion is a process in which a method calls itself until a base condition is met. To find the GCD of the two numbers using recursion, the Euclidean Algorithm is used. This method is elegant and concise because it uses the natural recursive structure of the Euclidean algorithm.

For example, to find the GCD of 27 and 18, the function gcd(), having the base case as if b==0: return a, is used. We call the function gcd(27,18), and since 18 is not zero, we call the function again with (18, 27 % 18), which is (18, 9). Again, we call gcd(9, 0) because 18 % 9 is 0. At this point, the second number is zero, so we return the first number, which is 9, and this value is then passed back through each previous function call, giving us the final result as 9.

Pseudo-code:

function gcd(a, b):
    if b == 0: // Base case
        return a
    else:
        return gcd(b, a % b) // Recursive case

Code:

Output:

Explanation: In the above Java program, the GCD of 27 and 18 is found using recursion.

Method 5: GCD of Both Positive and Negative Numbers

Mainly, the GCD is defined for positive numbers, but in real-world case scenarios, there can be a situation where you have to find the GCD of negative numbers also. In this case, you first find the absolute value of both numbers before applying any GCD-finding method (loop, recursion, Euclidean algorithm, etc.).

Code:

Output:

Explanation: In the above Java program, the GCD of the numbers -54 and 24 is calculated by first taking the absolute value of both of them and then using the Euclidean Algorithm.

Stein’s Algorithm to Find the GCD of Two Numbers

Stein’s Algorithm is a method to find the GCD of two numbers using only subtraction and bitwise operations. It is faster than Euclid’s Algorithm because division and modulus operations are replaced with simple shifts and subtraction. Some key points about the Stein’s algorithm are:

• If both the numbers are even, then GCD(a,b)=2×GCD(a/2,b/2).
• If one number is even and the other is odd, then divide the even number by 2.
• If both numbers are odd, then subtract the smaller number from the larger one.

Pseudo-code:

function gcd_stein(a, b):
    if a == b:
        return a
    if a == 0:
        return b
    if b == 0:
        return a
    if both a and b are even:
        return 2 * gcd_stein(a/2, b/2)
    if a is even:
        return gcd_stein(a/2, b)
    if b is even:
        return gcd_stein(a, b/2)
    if a > b:
        return gcd_stein((a - b)/2, b)
    else:
        return gcd_stein((b - a)/2, a)

Code:

Output:

Explanation: In the above Java program, the numbers 48 and 18 are used to find the GCD using Stein’s Algorithm. First, both numbers are checked to see if they are even or not using (a & 1) == 0 and (b & 1) == 0, which verifies if their last binary bit is 0. If both are even, they are divided by 2, and the process continues until the GCD is found.

Time and Space Complexity

Below is the time and space complexity of the different methods we have discussed so far.

Note: The time complexity of finding the GCD of negative and positive numbers depends on the method you are using.

Real-Life Applications of GCD

Below are some of the real-world applications of the GCD.

• Finding the Least Common Multiple (LCM): If you know the GCD, you can find the LCM of the two numbers by using the formula, LCM=a*b/GCD
• Dividing Resources or Items Evenly: When you are splitting the items into equal groups, GCD helps you to find the greatest possible size.
• Computer Graphics and Image Processing: It is used to determine the optimal scaling factors when resizing the images while maintaining their aspect ratio. By calculating the GCD of the image’s width and height, you can find the smallest proportional dimensions to prevent distortion
• Network Addressing (CIDR Notation): In networking, the GCD helps you to determine the common subnet mask when combining or dividing networks.
• Efficient Memory Allocation: In low-level programming and embedded systems, GCD can be used to determine the optimal block sizes for memory location, as it helps you find the largest memory block size.
• GCD in Cryptography (RSA Algorithm): In RSA encryption, the GCD is important for generating keys for the public and private keys, as they require a number e that is combined with Euler’s totient. To ensure coprimality, the GCD of e and φ(n) must be 1. This ensures secure encryption and decryption.
• GCD in Simplifying Fractions: By dividing both numerator and denominator by the GCD, you will get an equivalent fraction in the simplest form.

Conclusion

From the above article, we learned that finding the GCD of two numbers is a mathematical operation with wide-ranging applications in computing, networking, cryptography, and everyday problem-solving. Java offers multiple methods, from basic loops and recursion to advanced algorithms like Euclidean and Stein’s methods, each of which varies in efficiency and complexity. While loop-based methods are simple to understand, the Euclidean algorithm (especially the division version) is highly efficient and widely preferred. Java’s built-in BigInteger.gcd() makes handling large numbers effortless, and considering absolute values allows working with negative inputs as well. By understanding these methods and their complexities, developers can choose the most suitable one for their use case, ensuring both correctness and performance.

If you want to learn more about Java, you can refer to our Java Course.

GCD of Two Numbers in Java – FAQs