LCM(least common multiply)

Let's talk about algorithms!

Moderator: Board moderators

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

LCM(least common multiply)

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?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

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
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

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:)

Post Reply

Return to “Algorithms”