LCM of n numbers using prime factorisation

general
,
1

I am trying to calculate LCM of n numbers using prime factorisation method
i have written code for 4 numbers

this is my code

i just want to know that what is the more efficient way or if my method is optimized??

  1. first i am finding prime factors of given number
  2. then i am using a max array to hold the maximum power of esch prime factor
  3. and then i am using these values to calculate lcm

P.S I got this method from

http://discuss.codechef.com/questions/47240/sgarden-editorial

thanks…

2

u can actually make 2 optimizations as far as i can see…

  1. Calculate the primes b4 hand using Sieve of Eratosthenes!!!

  2. For calculating the powers u can use Exponential by Squaring!!!

U can find the implementation of the LCM part in my code for the problem u have mentioned…LINK…hope this helps…:slight_smile:

1 Like
3

Thanks for suggesting the optimizations
it really helped.

1 Like