Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have n numbers 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 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 upto 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/

share|improve this question
    
I think cross-posting in Stackoverflow would be a good idea. –  user2468 Mar 17 '12 at 18:52
    
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}$. –  TMM Mar 17 '12 at 18:54
    
@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. –  code_hacker Mar 17 '12 at 19:07
add comment

2 Answers

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.

share|improve this answer
    
I have tried reducing a[i] by dividing it by prime but still it's not giving result in required time. –  code_hacker Mar 17 '12 at 19:47
    
In the worst case all your numbers $a[i]$ are products of two prime factors a bit less than $10^6$, all distinct. Then I connot see how you could find the list of all these prime factors without factoring all of the $a[i]$ individually, and this probably cannot be done much faster than trying all possible prime candidates. In other words, I don't see what secret math theorem could help you unless it is an efficient factoring method, but this is known to be quite hard (though doable for the numbers in the range you give) –  Marc van Leeuwen Mar 17 '12 at 20:03
add comment

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);
share|improve this answer
    
Please explain the logic.I don't know Maple.I'm a c/c++ programmer. –  code_hacker Mar 17 '12 at 18:39
    
@code_hacker program calculates lcm using for loop and after that searches for prime factors of lcm using command ifactors... –  pedja Mar 17 '12 at 18:44
    
This could get incredibly large, incredibly quickly. I would be surprised if this ran faster than the pseudocode presented by the OP. In fact, if we chose 100 different primes of order about $10^{11}$, then your ifactor should have a very hard time. –  mixedmath Mar 17 '12 at 18:47
    
@code_hacker: In short, he calculates the LCM of the entire list and then factors it. –  mixedmath Mar 17 '12 at 18:48
    
This is certainly not more efficient. Using $n$ sieves of primes of size at most $10^6$ (as code_hacker suggests) is faster than $1$ sieve of primes of size at most $10^{6n}$. –  TMM Mar 17 '12 at 18:49
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.