Page 1 of 1

LCM(least common multiply)

Posted: Wed Aug 09, 2006 8:36 am
by Giorgi
Given n(n<1000) integers. Each integer is less than 1000.
Can anybody help me to find LCM of given numbers fast?

Posted: Wed Aug 09, 2006 8:47 am
by shamim
Well I don't know how fast you want it, but the following will give the result in a reasonable time.

LCM(a,b) = a*b/GCD(a,b).

now LCM (a,b,c) = LCM ( LCM(a,b), c );

I hope you get the idea.

Posted: Wed Aug 09, 2006 8:52 am
by mf
You can factorize each number and use the fact, that the exponent of a prime p in factorization of LCM is the maximum of exponents of that prime in factorizations of given numbers.

Posted: Wed Aug 09, 2006 9:15 am
by Giorgi
shamim wrote:Well I don't know how fast you want it, but the following will give the result in a reasonable time.

LCM(a,b) = a*b/GCD(a,b).

now LCM (a,b,c) = LCM ( LCM(a,b), c );

I hope you get the idea.
Thank you, but I wil have to find gcd of two numbers where one of them is very big.

Posted: Wed Aug 09, 2006 9:21 am
by Giorgi
mf wrote:You can factorize each number and use the fact, that the exponent of a prime p in factorization of LCM is the maximum of exponents of that prime in factorizations of given numbers.
Thaks for good idea. I wil try to solve this problem such way. It's easy. I'll have to do only multiply operations with big integers:)