### 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?

Can anybody help me to find LCM of given numbers fast?

The UVa Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=22&t=11494

Page **1** of **1**

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?

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.

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**

Thank you, but I wil have to find gcd of two numbers where one of them is very big.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.

Posted: **Wed Aug 09, 2006 9:21 am**

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