0

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

4
Contributors
7
Replies
8
Views
7 Years
Discussion Span
Last Post by ArkM
0

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

0

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

0

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

0

Even the method got by googling doesnt work..

it also gives me a Time limit exceeded

0

@Siddhant

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

0

...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.
Take the time to help us to help you. Please be thoughtful and detailed and be sure to adhere to our posting rules.