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?

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 :)

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))

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.

Thanks Nick, but I need the lowest common factor, not the greatest common denominator ;)

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.

To find the lcm (least common multiple) do
(36 * 45) / gcd(36, 45)

I knew I was calling it by the wrong name :) Thanks Nick, that works!

>> gcd(x,y)

and just how do we get the greatest common denominator?

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;
}

---