## LCM(least common multiply)

Moderator: Board moderators

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

### LCM(least common multiply)

Given n(n<1000) integers. Each integer is less than 1000.
Can anybody help me to find LCM of given numbers fast?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi
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
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi
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:)