suppose we are given N numbers a1,a2,a3....aN. Now how to write a program which calculates the Lcm of these numbers.....
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
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.
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.
lcm(2, 2, 2) * gcd(2, 2, 2) != 2*2*2
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.
lcm(a,b) = a*b/gcd(a,b)
lcm(a1,a2,...an) = lcm(a1,lcm(a2,lcm(a3,lcm(... , an))))
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
Integer overflow while calculating a*b. Use a/gcd(a,b)*b instead.
but an int can store upto 2X10^9 then how can overflow take place..
lcm(2..19) = 232792560
232792560*20 > 4e9.
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
Every time you multiple think about maximum value. cast it to int64, if you need
this is really helpful