Calculating GCD and LCM of Numbers Using Java with Optimal Time Complexity

Calculating the greatest common divisor (GCD) and least common multiple (LCM) of numbers is a fundamental task in number theory and has numerous applications in various domains. To efficiently compute the GCD and LCM of numbers using Java, ensuring the most optimized time complexity. We will provide explanations of the algorithms used, present a Java implementation, and demonstrate examples to solidify our understanding.

Calculating the GCD using Euclidean Algorithm:
The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The Euclidean algorithm is a widely-used approach to calculate the GCD efficiently.

Here’s the Java implementation for calculating the GCD using the Euclidean algorithm:

public class GCDandLCM {
    public static int calculateGCD(int a, int b) {
        if (b == 0)
            return a;
        return calculateGCD(b, a % b);
    }

    public static int calculateLCM(int a, int b) {
        int gcd = calculateGCD(a, b);
        return (a * b) / gcd;
    }

    public static void main(String[] args) {
        int num1 = 24;
        int num2 = 36;

        int gcd = calculateGCD(num1, num2);
        int lcm = calculateLCM(num1, num2);

        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd);
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm);
    }
}

Explanation of the Implementation:
The calculateGCD method takes two parameters, a and b, representing the numbers for which we want to find the GCD. It uses the Euclidean algorithm recursively until the remainder (a % b) becomes zero. At that point, the GCD is found, and the algorithm returns the value of b.

The calculateLCM method takes two parameters, a and b, similar to the calculateGCD method. It calls the calculateGCD method to find the GCD of a and b and then uses the formula LCM = (a * b) / GCD to calculate the LCM.

In the main method, we define two numbers, num1 and num2, for which we want to calculate the GCD and LCM. We then call the respective methods and print the results.

Examples:
Let’s explore a few examples to understand the concept better:

Example 1:
Calculate the GCD and LCM of 24 and 36:
num1 = 24, num2 = 36
The GCD is 12, and the LCM is 72.

Example 2:
Find the GCD and LCM of 10 and 15:
num1 = 10, num2 = 15
The GCD is 5, and the LCM is 30.

Example 3:
Calculate the GCD and LCM of 48 and 60:
num1 = 48, num2 = 60
The GCD is 12, and the LCM is 240.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top