red_coder's blog

LCM.....
By red_coder, 13 years ago, In English

suppose we are given N numbers a1,a2,a3....aN. Now how to write a program which calculates the Lcm of these numbers.....

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

lcm(a1,a2) = a1 * a2 / gcd(a1,a2).

lcm(a1,a2,a3) = lcm( lcm(a1,a2) , a3).

And then continue this process for all numbers.

→ Reply
»
13 years ago, # |
← Rev. 4   Vote: I like it -10 Vote: I do not like it

You can calculate their GCD and use this formula: LCM(a1,...,aN)*GCD(a1,...,aN) = a1*a2*...*aN

UPD: Oh, sorry it's really incorrect.

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    lcm(2, 2, 2) * gcd(2, 2, 2) != 2*2*2

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    This formula isn't correct. For example, a1 = 2, a2 = 4, a3 = 5. LCM(a1,a2,a3) = 20, GCD(a1,a2,a3) = 1, a1*a2*a3 = 40. And LCM(a1,a2,a3) * GCD(a1,a2,a3) != a1*a2*a3.

    → Reply
»
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it

lcm(a,b) = a*b/gcd(a,b)

lcm(a1,a2,...an) = lcm(a1,lcm(a2,lcm(a3,lcm(... , an))))

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    i have used the same concept.... for calculating the lcm of first 20 natural numbers my code is as follows... but the answer is not coming correct

    int gcd(int a, int b)
{
    if(b==0)
    return a;
    else
    return gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}

int main()
{
    int ans=2;
    for(int i=3;i<=20;i++)
    {
        ans= lcm(ans,i);
    }
    cout<<ans<<"\n";
    return 0;
}
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Integer overflow while calculating a*b. Use a/gcd(a,b)*b instead.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but an int can store upto 2X10^9 then how can overflow take place..

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          lcm(2..19) = 232792560

          232792560*20 > 4e9.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            thanks a lot Hohol i finally got it right.. by the way i want to tell u that i have suffered a lot due to integer overflows... how to improve my mistakes for overflows??? can u suggest me something

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Every time you multiple think about maximum value. cast it to int64, if you need

              → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it -29 Vote: I do not like it

        this is really helpful

        → Reply