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: