I wanted to know an efficient algorithm to calculate the product of divisors..
My brute force method is giving me a Time limit exceeded.

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)...

...in a few milliseconds...

All the best with the coding competition... And You really shud have used Google.

I guess that Bruteforce doesnt work because of the Constrictions put up by that competition

>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 ).

@Siddhant

Its not just 100 cases
The maximum being around 300000 test cases and the time limit is 2 seconds.

...The maximum being around 300000 test cases and the time limit is 2 seconds.

~6 microseconds to generate number upto 400 digits (for max 1 million)...
Hmm... It's interesting...
And where is this megabytes file target?

This article has been dead for over six months. Start a new discussion instead.