GCD & LCM Architect

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), of two or more non-zero integers, is the largest positive integer that divides each of the integers without a remainder.

Real World Example:

Imagine you have 24 apples and 36 oranges. You want to group them into identical fruit baskets with no fruit left over. The GCD of 24 and 36 is 12. You can create 12 baskets, each containing 2 apples (24/12) and 3 oranges (36/12).

Prime Factorization Method:

1. Find the prime factors of each number.

2. Identify common prime factors.

3. Multiply the lowest powers of these common factors.

The Least Common Multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers.

Real World Example:

Planet A orbits a star every 4 years. Planet B orbits the same star every 6 years. If they are aligned today, when will they align again? The LCM of 4 and 6 is 12. They will realign in exactly 12 years.

The Absolute Formula:

A powerful property links LCM and GCD. If you know the GCD, finding the LCM is instantaneous using this formula (as rendered in our calculator):

Instead of calculating prime factors (which is very slow for huge numbers), our enterprise engine uses the Euclidean Algorithm—one of the oldest algorithms still in common use, invented around 300 BC.

The Principle: The GCD of two numbers also divides their difference. This allows us to repeatedly replace the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero.

function euclideanGCD(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

This operates in O(log(min(a,b))) time complexity, making CalcSuit blisteringly fast even for 15-digit numbers.