I can't understand why your brutal force algorithm is so expensive (apropos, where is this algorithm? ;))

Numbers in range 1..1000000 have less than ~65 divisors. It's so easy to get all divisors by brutal force test (n%k == 0) then (or on the fly) to multiply some tens of these numbers with any big integers package (less than 200 digits)...

>I can't understand why your brutal force algorithm is so expensive
It will certainly not be. But he may be getting 100 of Input tests at once. So it may exceed the time limit ( which is about 2-3 seconds ).