Thread: Lowest Common Factor

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    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?

  2. #2
    Registered User Nippashish's Avatar
    Join Date
    Sep 2002
    Posts
    34
    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

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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))

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Thanks Nick, but I need the lowest common factor, not the greatest common denominator

  6. #6
    Registered User
    Join Date
    May 2002
    Posts
    49
    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.
    Hello, everyone.

  7. #7
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    To find the lcm (least common multiple) do
    (36 * 45) / gcd(36, 45)

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I knew I was calling it by the wrong name Thanks Nick, that works!

  9. #9
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    937
    >> gcd(x,y)

    and just how do we get the greatest common denominator?
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  10. #10
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C program for finding highest common factor!!
    By visham in forum C Programming
    Replies: 11
    Last Post: 08-02-2007, 07:10 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. reducing a fraction/greatest common factor
    By dbaryl in forum C Programming
    Replies: 2
    Last Post: 07-21-2002, 03:05 PM
  4. Greatest Common Factor
    By NavyBlue in forum C Programming
    Replies: 5
    Last Post: 06-11-2002, 02:47 PM
  5. Greatest Common Factor problem
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 10-08-2001, 03:29 PM