Discussion @ 1204. Idempotents @ Timus Online Judge

Yes,I know all this.My algorithm is O(sqrt(n)),but I got Time Limited exceeded.The program uses only 1.5 sec at my computer when K=1000 and the dataset is random.It will cost also O(sqrt(n)) to get p

Posted by Blue cat 19 Mar 2002 15:46

Use precalc. array of all primes <= sqrt(10^9), I think ur program'll be much faster

Posted by I have answers to all your questions :) 19 Mar 2002 15:57

You think I'm so fool.Of course,I know such trick.Maybe the timelimit is too strict.I'll try more

Posted by Blue cat 19 Mar 2002 15:59

> >

This problem has a solution fastre than O(sqrt(N))

Posted by Leonid Volkov 20 Mar 2002 11:41

It has a pure analitical solution with almost no cycles needed :-)
The test are specially made so to do not allow all the possible O(sqrt
(N)) solutions pass!

Discussion of Problem 1204. Idempotents