Блог пользователя red_coder

Автор red_coder, 13 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
13 лет назад, # |
Rev. 4   Проголосовать: нравится -10 Проголосовать: не нравится

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.

  • »
    »
    13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

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

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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;
    }
    
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          lcm(2..19) = 232792560

          232792560*20 > 4e9.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится -29 Проголосовать: не нравится

        this is really helpful