How to calculate all the prime factors of lcm of n integers?

Question

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

I have a method but I need a more efficient one.

My method:

 First calculate all the prime numbers up to 10^6 using sieve of Eratosthenes.

 For each a[i]
      bool check_if_prime=1;
      For all prime <= sqrt(a[i])
             if a[i] % prime[i] == 0 {
                store prime[i]
                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 prime[i]'s

Is there any better approach to this problem?

I'm posting the link to the problem:

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

Link to my code: http://pastebin.com/R8TMYxNz

Solution:

As suggested by Daniel Fischer my code needed some optimizations like a faster sieve and some minor modifications. After doing all those modification, I'm able to solve the problem. This is my accepted code on SPOJ which took 1.05 seconds:

#include<iostream>
#include<cstdio>
#include<map>
#include<bitset>

using namespace std;

#define max 1000000

bitset <max+1> p;
int size;
int prime[79000];

void sieve(){
    size=0;
    long long i,j;
    p.set(0,1);
    p.set(1,1);
    prime[size++]=2;
    for(i=3;i<max+1;i=i+2){
        if(!p.test(i)){
            prime[size++]=i;
            for(j=i;j*i<max+1;j++){
                p.set(j*i,1);
            }
        }
    }
}

int main()
{
    sieve();

    int t;
    scanf("%d", &t);

    for (int w = 0; w < t; w++){
        int n;
        scanf("%d", &n);
        long long a[n];

        for (int i = 0; i < n; i++)
            scanf("%lld", &a[i]);

        map < long long, int > m;
        map < long long, int > ::iterator it;
        for (int i = 0; i < n; i++){
            long long num = a[i];
            long long pp;
            for (int j = 0; (j < size) && ((pp = prime[j]) * pp <= num); j++){
                int c = 0;
                for ( ; !(num % pp); num /= pp)
                    c = 1;
                if (c)
                    m[pp] = 1;
            }

            if ((num > 0) && (num != 1)){
                m[num] = 1;
            }
        }
        printf("Case #%d: %d\n", w + 1, m.size());
        for (it = m.begin(); it != m.end(); it++){
            printf("%lld\n", (*it).first);
        }
    }

    return 0;
}

In case, anyone is able to do it in a better way or by some faster method, please let me know.

Answer 1

With those constraints, a few not too large numbers, the best way to find the prime factorisation of their least common multiple is indeed the factorisation of each number. Since there are only 78498 primes below 10⁶, trial division will be fast enough (unless you're really desperate for the last drop of performance), and sieving the primes to 10⁶ is also a matter of few milliseconds.

If speed is of the utmost importance, a combined approach of trial division and a deterministic Miller-Rabin type prime test with a factorisation method like Pollard's rho-algorithm or an elliptic curve factorisation method is probably a bit faster (but the numbers are so small that the difference won't be large, and you need a number type with more than 64 bits for the primality test and factorisation to be fast).

In the factorisation, you should of course remove the prime factors as they are found

if (a[i] % prime[k] == 0) {
    int exponent = 0;
    do {
        a[i] /= prime[k];
        ++exponent;
    }while(a[i] % prime[k] == 0);
    // store prime[k] and exponent
    // recalculate bound for factorisation
}

to reduce the limit to which you need to check the primes.

Your main problem, as far as I can see, is that your sieve is too slow and uses too much space (which is in part responsible for its slowness). Use a bit sieve to get better cache locality, remove even numbers from the sieve and stop checking whether to cross off multiples at the square root of max. And you're allocating way too much space for the prime array.

for(int j=0;(prime[j]*prime[j] <= num) && (j<size);j++){

You must check j < size before accessing prime[j].

    while(num%prime[j]==0){
        c=1;
        num /= prime[j];
        m[prime[j]]=1;
    }

Don't set m[prime[j]] multiple times. Even if std::maps are pretty fast, that's slower than setting it only once.