Here is *the algorithm* for finding GCF of 2 numbers...
Code:
int GCF (int i1, int i2)
{
int i3;
for (;;)
{
i3 = difference between i1 and i2;
if (i3 == 0) break;
bigger of i1 and i2 = i3;
}
return i1;
}
Let's run through this code...
Code:
i1: 27 27 18 9
i2: 36 9 9 9
i3: 9 18 9 0 ... return 9;
Code:
i1: 96 69 42 15 15 3 3 3 3
i2: 27 27 27 27 12 12 9 6 3
i3: 69 42 15 12 3 9 6 3 0 ... return 3;
There are quicker ways to check when to terminate the loop, but this one does work.
Once you have the GCF of two numbers, finding the LCM is pretty simple...
LCM (a, b) = a * b / GCF (a, b)