I wanted to know an efficient algorithm to calculate the product of divisors..
My brute force method is giving me a Time limit exceeded.
catchmrbharath 0 Light Poster
Sky Diploma 571 Practically a Posting Shark
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 1,090 Postaholic
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 571 Practically a Posting Shark
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 1,429 Practically a Posting Shark
>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 0 Light Poster
Even the method got by googling doesnt work..
it also gives me a Time limit exceeded
catchmrbharath 0 Light Poster
@Siddhant
Its not just 100 cases
The maximum being around 300000 test cases and the time limit is 2 seconds.
ArkM 1,090 Postaholic
...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?
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.