### red_coder's blog

By red_coder, 12 years ago,

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

• 0

 » 12 years ago, # | ← 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.
 » 12 years ago, # | ← Rev. 4 →   -10 You can calculate their GCD and use this formula: LCM(a1,...,aN)*GCD(a1,...,aN) = a1*a2*...*aNUPD: Oh, sorry it's really incorrect.
•  » » 12 years ago, # ^ | ← Rev. 3 →   0 lcm(2, 2, 2) * gcd(2, 2, 2) != 2*2*2
•  » » 12 years ago, # ^ |   +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.
 » 12 years ago, # |   +5 lcm(a,b) = a*b/gcd(a,b)lcm(a1,a2,...an) = lcm(a1,lcm(a2,lcm(a3,lcm(... , an))))
•  » » 12 years ago, # ^ | ← 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<
•  » » » 12 years ago, # ^ |   +1 Integer overflow while calculating a*b. Use a/gcd(a,b)*b instead.
•  » » » » 12 years ago, # ^ |   0 but an int can store upto 2X10^9 then how can overflow take place..
•  » » » » » 12 years ago, # ^ |   +3 lcm(2..19) = 232792560232792560*20 > 4e9.
•  » » » » » » 12 years ago, # ^ |   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
•  » » » » » » » 12 years ago, # ^ |   +1 Every time you multiple think about maximum value. cast it to int64, if you need
•  » » » » 3 months ago, # ^ |   -29 this is really helpful