### Design an algorithm to find the GCD and LCM of two positive numbers

**Problem :**Design an algorithm to find the GCD (Greatest Common Divisor) of two positive numbers and use the same to find LCM of two positive numbers.

**Input:**Two Numbers

**Output :**Least Common Multiple of two numbers.

**GCD(NUM1, NUM2)**

Rem <-- NUM1 % NUM2 [% Modulus Operator]

Repeat While Rem <> 0

NUM1 <-- NUM2

NUM2 <-- Rem

Rem <-- NUM1 % NUM2

[End of While]

Return NUM2

Exit.

**LCM(NUM1, NUM2)**

Return (NUM1 * NUM2) / GCD( NUM1, NUM2)

Exit.

**NOTE**: Here in this example algorithm, finding LCM in the main problem that can be divided into sub-problem like finding the GCD first and using the same to solve the main problem. So, GCD algorithm is written first and than the other algorithm that can be divided into small problems and algorithm can be written to solve such small problems.

### Tracing

Suppose that the LCM algorithm is called using 12 and 16. The algorithm calls GCD with 12 and 16.Rem <-- 12 % 16 i.e. Rem= 12

Rem is not equal to zero. So, NUM1=16 and NUM2 =12

Rem<-- 16%12 i.e. Rem=4

Rem is not equal to Zero. So, NUM1 =12 and NUM2 =4

Rem <-- 12 % 4 i.e. Rem=0

Rem is equal to Zero.

So, GCD algorithm returns NUM2 that is 4.

When the algorithm LCM gets the result from GCD algorithm its find the expression value

(NUM1 * NUM2) / GCD (NUM1, NUM2). i.e. (12 * 16)/4

It is equal to 48. 48 is the LCM of 12 and 16

## Comments

## Post a Comment