What is pseudo code for LCD of two numbers?

Answer 1

The LCD (least common denominator) is better known more generally as the LCM (least common multiple). The LCM of any two integers, typically denoted LCM (a, b), is the lowest positive integer that is evenly divisible by both integers. That is, LCM (a, b) = c such that c/a = c/b. Division by zero is undefined thus it stands to reason that neither a nor b can be zero. However, many people regard LCM (a, 0) = a to be valid even though it is technically undefined, as is LCM (0, 0). Note that either a or b may be negative but LCM (a, b) must always be positive.

The product of a and b is obviously a common multiple of a and b. However, it is not necessarily the lowest common multiple. For instance, 20 is the product of 2 and 10 and is therefore a common multiple of 2 and 10. However, the lowest common multiple of 2 and 10 is 10 because 10/2 = 5 and 10/10 = 1. From this we can surmise that LCM (a, b) can be no greater than the product of a and b and it cannot be any less than the largest of a and b.

There are several ways to calculate the LCM of two integers, however one of the simplest is by reduction by the greatest common divisor (GCD). That is, GCD (a, b) = c such that a and b are evenly divisible by c. The GCD and LCM are similar types of problem, however the GCD is much easier to calculate and can be implemented efficiently using Euclid's algorithm.

In pseudo-code, we can write the GCD (Euclid) algorithm as follows:

algorithm GCD (a, b) is:

while (a <> b) do

if a > b then a := a - b else b := b - a

end while

return a

From this we can now write the LCM algorithm in terms of the GCD algorithm:

algorithm LCM (a, b) is: return a / GCD (a, b) * b

Note that a * b / GCD (a, b) produces the same result, however it is more efficient to perform the division before the multiplication. This is because a / GCD (a, b) is guaranteed to be an integer that is less than or equal to a and is therefore guaranteed not to overflow. Multiplying that integer by b may still overflow, however the chances of overflow are reduced compared to that of multiplying a and b prior to the division.