GCD Of Two Numbers In Java with Advanced Examples

This article is about GCD Of Two Numbers In Java will teach you how to use Java to find the GCD of two numbers. This is done with the help of the following program, using if else statements and for and while loops.

Furthermore, I will also provide an advanced examples in this article in order for you to easily understand this kind of topic that I will discuss.

What is GCD of two numbers in Java and why do we need it?

In Java, GCD stands for (Greatest Common Divisor). It is used to simplify fractions for better solutions. It is the highest number that can be used to divide two or more numbers into two equal parts. Its short name is GCD.

In addition, the GCD (Greatest Common Divisor) has many uses in number theory, especially in modular arithmetic and, by extension, encryption algorithms like RSA. It is also used for simpler applications, such as simplifying fractions.

Without further ado I will show you some advanced source code that uses different methods to get the GCD of two numbers.

Example program to find the GCD of two numbers using for loop and if statement

The following Java program uses the for loop and if statement below to find the GCD of two numbers that are stored on variable names number1 and number2 respectively.

In addition, the for loop will be executed until i is less than number1 and number2. In that matter, all the numbers within 1, the smallest of two numbers, will be iterated to find the GCD of the numbers.

Then when GCD is set to the number that is the largest, if both numbers 1 and 2 can be divided by i, this keeps executing until the greatest common divisor (GCD) of numbers 1 and 2 is found.

public class Main {

    public static void main(String[] args) {


        // find GCD between n1 and n2

        int number1 = 26, number2 = 233;


        // initially set to gcd

        int gcd = 1;

        for (int i = 1; i <= number1 && i <= number2; ++i) {


            // check if i perfectly divides both n1 and n2

            if (number1 % i == 0 && number2 % i == 0)

                gcd = i;

        }

        System.out.println("GCD of " + number1 + " and " + number2 + " is " + gcd);

    }

}

Output:

GCD of 26 and 233 is 1

Example program to find the GCD of two numbers using while loop and if else statement

The following program calculates the GCD of two numbers in Java using the while loop and if else statement. This method is a better way to find the GCD of two numbers because the result is subtracted from the bigger number, and the difference is put into the variable that holds the bigger number. This is done again and again until numbers 1 and 2 are the same.

public class Main {

    public static void main(String[] args) {


        // find GCD between n1 and n2

        int number1 = 26, number2 = 233;


        while (number1 != number2) {

            if (number1 > number2) {

                number1 -= number2;

            } else {

                number2 -= number1;

            }

        }

        System.out.println("GCD: " + number1);

    }

}

Output:

GCD: 1

Note: The two example programs only work if all the numbers you put in are positive. 

Example program to find the GCD of two numbers for both negative and positive

In the above two examples, we can only accept positive numbers, but in this following program they can accept both positive and negative smaller numbers.

public class GCD {

    public static void main(String[] args) {

        int number1 = 26, number2 = -233;

        // Always set to positive

        number1 = (number1 > 0) ? number1 : -number1;

        number2 = (number2 > 0) ? number2 : -number2;

        while (number1 != number2) {

            if (number1 > number2) {

                number1 -= number2;

            } else {

                number2 -= number1;

            }

        }

        System.out.println("GCD: " + number1);

    }

}

Output:

GCD: 1

Example program to find the GCD of two numbers using scanner

The following program uses the scanner method to find the GCD of two numbers. We can define a method named findGCD() so that we parse the two parameters num1 and num2, whose type is int.

import java.util.Scanner;

public class FindGCDExample4

{

    //private static Scanner sc;  

    public static void main(String[] args)

    {

        int num1, num2, gcd = 0;

        Scanner sc = new Scanner(System.in);

        System.out.print("Enter the First Number: ");

        num1 = sc.nextInt();

        System.out.print("Enter the Second Number: ");

        num2 = sc.nextInt();

        gcd = findGCD(num1, num2);

        System.out.println("GCD of " + num1 + " and " + num2 + " = " + gcd);

    }

    public static int findGCD(int num1, int num2)

    {

        while (num2 != 0)

        {

            if (num1 > num2)

            {

                num1 = num1 - num2;

            } else

            {

                num2 = num2 - num1;

            }

        }

        return num1;

    }

}

Output:

Enter the First Number: 12

Enter the Second Number: 12

GCD of 12 and 12 = 12

Example program to find the GCD of two numbers using recursion

The following program using recursion takes two positive integers to find the GCD of two numbers.

 public class GCD {

     public static void main(String[] args) {

         int number1 = 26, number2 = 233;

         int hcf = hcf(number1, number2);



         System.out.printf("G.C.D of %d and %d is %d.", number1, number2, hcf);

     }

     public static int hcf(int number1, int number2)

     {

         if (number2 != 0)

             return hcf(number2, number1 % number2);

         else

             return number1;

     }

 }

Output:

G.C.D of 26 and 233 is 1.

Example program to find the GCD of two numbers using modulo operator

The following program uses the modulo operator to find the GCD of two numbers using the function named findGCD(). Two parameters will be parsed, num1 and num2. All the numbers should be type int. If the second number (num2) is 0 GCD, the method returns a GCD. If num2 is not 0, it returns num1%num2.

public class PIESGCD

{

    public static void main(String[] args)

    {

        int num1 = 26, num2 = 233;

        System.out.println("GCD of " + num1 + " and " + num2 + " is " + findGCD(num1, num2));

    }

    //recursive function to return gcd of a and b  

    static int findGCD(int num1, int num2)

    {

        if (num2 == 0)

            return num1;

        return findGCD(num2, num1 % num2);

    }

}

Output:

GCD of 26 and 233 is 1

Conclusion

I hope this article has helped you learn a lot. Check out my previous and latest articles for more life-changing tutorials which could help you a lot.

Java numeric operations

• Primitive types. int (32-bit), long (64-bit), double (64-bit float), BigInteger (unlimited).
• Math class. Static methods for common operations: abs, max, min, pow, sqrt, floor, ceil.
• BigDecimal. Required for money and precise decimals , never use double for currency.
• Integer overflow. int overflow silently wraps around. Use Math.addExact / multiplyExact to throw on overflow, or use long.
• Random. Random for general use, ThreadLocalRandom for high-concurrency, SecureRandom for security.

Working code example

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Random;

public class NumericPatterns {
    // GCD using Euclid's algorithm
    public static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    // LCM = (a * b) / gcd(a, b)
    public static long lcm(long a, long b) {
        return Math.abs(a / gcd(a, b) * b); // avoids overflow
    }

    // BigDecimal for money math
    public static BigDecimal totalWithTax(BigDecimal price, BigDecimal taxRate) {
        return price.add(price.multiply(taxRate));
    }
}

Common pitfalls

• Using double for money. Floating-point rounding causes $0.10 to store as 0.09999… , use BigDecimal.
• Integer overflow. int MAX_VALUE + 1 wraps to MIN_VALUE. Use long or Math.addExact.
• Division by zero. Integer division throws ArithmeticException. Double division returns Infinity or NaN.

Best practices

• Use BigDecimal for currency. Always.
• Use Math.addExact / multiplyExact when overflow would be a bug.
• Use SecureRandom for tokens, keys, and any security-sensitive random value.

Glenn Azuelo

Programmer & Technical Writer at PIES IT Solution

Glenn Azuelo is a programmer and writer at PIES IT Solution, author of 40+ PHP tutorials, Java capstone projects, and Python game guides at itsourcecode.com. Specializes in PHP built-in functions (string manipulation, arrays, filesystem, magic methods), Java Windows Forms projects for BSIT capstone (chat application, POS, faculty management, memory game), and Python game programming with Pygame (chess, blackjack, dice).

Expertise: PHP, PHP Tutorials, PHP Built-in Functions, PHP String Functions, PHP Array Functions, PHP Magic Methods, Java, Java Swing, Windows Forms, Python, Pygame, Capstone Projects  ·  View all posts by Glenn Azuelo →