I also got ACC on this problem.
First I precalculate the first several primes using the Sieve Method.
Actually I precalculate all primes which are smaller than 40 000.
They are about 4200 so this is enough for us for this problem.
Then I simply use simulation technique. And the only optimization
I do is that I cache the results for the input numbers my
program receives ( as we have a small range for
possible input values 1<=N<=3501 ). This way I never simulate
the process for more than once for a given input number N.
But my program is very slow
It got a runtime of about 1 min
on the Online Judge Machine. So ... My question is if there's some
direct formula, which we could use. I doubt it as we have to
deal with primes. Then there should be a better method/algorithm
for solving this problem.
How can other people get a runtime of 0.000 sec? Does
that mean they have just precalculated all the answers
for N = 1,2,...3501 and after that they have just hardcoded
these answers in a second program which they have submitted
to the Judge.
Or ... Is there really some nice solution ( algorithm ) which
could decrease the runtime to let's say several
seconds ( 1 sec, 5 secs or even 10 secs would be perfect ).
Obviously using only a simulation technique we get