Page 1 of 1

### LCM(least common multiply)

Posted: Wed Aug 09, 2006 8:36 am
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
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
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
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
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:)