# Lowest Common Factor

• 12-21-2002
PJYelton
Lowest Common Factor
Arghh... I think thats the right name for it! Does anyone know of an easy way to find the lowest common factor between two integers? Like the lowest common factor of 6 and 8 is 24. I'm writing a fractions class that when it adds and subtracts needs to find the lowest common factor of the denominators. I know I could do:
Code:

```counter=greater(x,y); while (counter%x || counter%y)   counter++;```
but this seems very inefficient. From my math days I remember one multiplies all the factors the two numbers don't have in common, but I really think that would be too hard to write code for. Anyone know of more efficient way?
• 12-21-2002
Nippashish
Is there any reason that you need the lowest common factor? If you're just adding/subtracting fractions any common factor would do. So unless there is an actual need for the LOWEST common factor I would just use the product of the denominators (sp?), computers don't have problems with big numbers :)
• 12-21-2002
Nick
Use elucid's algorithm
gcd(a, b) = gcd(b, r) where r = a % b.
So to put a/b in lowest terms

(a / gcd(a, b)) / (b / gcd(a, b))
• 12-21-2002
PJYelton
Thats true, that is faster :)

I was hoping there was a better way of doing it, like how one finds a greatest common denominator by simply doing:
Code:

```int dummy=0;    while (u) {     dummy=u;     u=v%u;     v=dummy; } return v;```
I'm beginning to think that there isn't an easier way though...

And yeah, using the products of the denominators runs into problems. The denominators quickly get too big for a long variable, and if I use floats then its a real pain to simplify the fraction since I can't use the modulus operator anymore.
• 12-21-2002
PJYelton
Thanks Nick, but I need the lowest common factor, not the greatest common denominator ;)
• 12-21-2002
Hotman_x
I think COMMON MULTIPLE is what you need. Not COMMON FACTOR.

9 is max common factor of 36 and 45;
180 is min common multiple of 36 and 45.
• 12-22-2002
Nick
To find the lcm (least common multiple) do
(36 * 45) / gcd(36, 45)
• 12-22-2002
PJYelton
I knew I was calling it by the wrong name :) Thanks Nick, that works!
• 12-22-2002
CodeMonkey
>> gcd(x,y)

and just how do we get the greatest common denominator?
• 12-23-2002
PJYelton
The easiest way is to use the function I have written a little higher up which uses Euclids Theorem.
Code:

```int gcd(int u, int v) {   int dummy=0;      while (u)   {       dummy=u;       u=v%u;       v=dummy;   }   return v; }```