0
$\begingroup$

I have $n$ numbers stored in an array $a$, say $a[0],a[1],.....,a[n-1]$ where each $a[i] \leq10^{12}$ and $n < 100$ . Now,I need to find all the prime factors of the $lcm$ of these $n$ numbers i.e., $lcm$ of $\{a[0],a[1],.....,a[n-1]\}$

I have a method but I need more efficient one.

My method :

 First calculate all the prime numbers up to $10^6$ using sieve of Eratosthenes.   For each a[i]       For all p prime <= sqrt(a[i])              bool check_if_prime=1;              if a[i] % p == 0 {                 store p                 check_if_prime=0              }              if check_if_prime                 store a[i]     // a[i] is prime since it has no prime factor <= sqrt(n)    Print all the stored primes 

Is there any better approach to this problem ?

This is the link to the problem:

http://www.spoj.pl/problems/MAIN12B/

  • 0
    I think cross-posting in [Stackoverflow](http://stackoverflow.com/) would be a good idea.2012-03-17
  • 0
    I think your method is quite efficient. Maybe you could achieve some speedups here and there, e.g. if you find a factor $p$ of $a[i]$, then you can continue with factoring $a[i]/p$ instead of $a[i]$. So you then only have to continue with primes less than $\sqrt{a[i]/p}$.2012-03-17
  • 0
    @TMM : I tried it bur it's not working.It seems I need a fresh new efficient algorithm based on some mathematical theorem which can reduce the time of computation to a much larger extent.2012-03-17

2 Answers 2