How to calculate all the prime factors of $lcm$ of $n$ numbers?

Question

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/

Answer 1

Perhaps this Maple program is good solution for your problem :

L:=[4*10^7,3*10^9,2*10^6,10^8]:
LCM:=1:
for n in L do
LCM := ilcm(LCM,n):
end do;
ifactors(LCM);

Answer 2

Apparently you are only interested in the set of prime factors, not their multiplicity in the LCM. In other words you need those prime numbers that divide at least one of the $a[i]$. Then you could just traverse the prime numbers $p$ just once, in increasing order, and divide all the $a[i]$ by $p$; whenver the division is exact you can replace $a[i]$ by $a[i]/p$ (and repeat, so the all fectors $p$ get eliminated), and if this happens at least once, $p$ can be retained as prime factor of the LCM. If you are interested in the multiplicity of $p$ after all, this is easy to record during this loop as well: it is the maximum number of factors $p$ found in one same $a[i]$. Once one of the $a[i]$ becomes less than $p^2$ (either by division or because $p$ grows) it can itself be added to the the list of prime numbers, and removed from the collection of $a[i]$ to test. Keep a linked list of candidates that are left over, and stop when it becomes empty.

The advantage of this approach is that for $a[i]$ that are large but contain a lot of small prime factors, they are reduced in size rapidly and hence can be removed from the search relatively fast. You can get the same advantage in your proposed approach if you divide $a[i]$ by $p$ once you find that te remainder is $0$. However, some work is then still required to prune multiply stored prime factors.