product of divisors

[catchmrbharath]

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

[Sky Diploma]

Google is your friend.

http://www.mathlinks.ro/viewtopic.php?t=277509
http://en.wikipedia.org/wiki/Divisor_function
I guess you can use that there. :)

I guess you guys need it for the coding competition.
http://www.codechef.com/JUNE09/problems/D1/

[ArkM]

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

[Sky Diploma]

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

[siddhant3s]

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

[catchmrbharath]

Even the method got by googling doesnt work..

it also gives me a Time limit exceeded

[catchmrbharath]

@Siddhant

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

[ArkM]

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