LCM(least common multiply)

Giorgi · Post by **Giorgi** » 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?

shamim · Post by **shamim** » 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.

mf · Post by mf » 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.

Giorgi · Post by **Giorgi** » 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.

Giorgi · Post by **Giorgi** » 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:)