Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

PRIMES - Printing primes

Print all prime numbers from 0 to 1000000.

No input

Output

All primes from range [0;1000000].

No example

Special thanks to numerix for the concept of this task.


Added by:Piotr Kąkol
Date:2010-04-21
Time limit:35s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC SCM qobi VB.NET

hide comments
2021-07-28 02:48:53
.22 seconds in JAVA using sieve of eratosthenes and BitSet
2014-02-14 23:03:18 Dominique VAILLANT
@Mitch 36 in Ruby?! Superb! I'm searching...
2010-05-02 10:08:26 Piotr KÄ…kol
@Zoltán Zámbori - Too much a bit. ;-)

@debanjan - Thanks for this useful information. :-)
2010-04-27 19:33:47 :(){ :|: & };:

Piotr I think the judge doesn't work in the way you are thinking :)

Take for example this task TDPRIMES and TDKPRIME,my AC solutions gives TLE if I try re-submitting in congestion that is when the judge is checking some other solutions.

The submission id:3570850 and id:3570849,I resubmitted both of my AC solution simultaneously which now gives TLE. ;-)

You may experiment this with any other two problems from your solution set :-)




Last edit: 2010-04-27 20:04:53
2010-04-27 19:16:22 Zoltán Zámbori
I don't know, but i'm able to send some numbers. Printing primes with the regexp:
2.. 2500 needs 1sec
2.. 5000 needs 4.3sec
2.. 7500 needs 11sec
2..10000 needs 22sec
2..12500 needs 38sec
2..15000 needs 60sec
2..17500 needs 92sec
2..20000 needs 130sec


Last edit: 2010-04-28 06:32:27
2010-04-27 16:12:34 Piotr KÄ…kol
@Debanjan - You won. ;-) Good for You!
But if someone sent a slow submission SPOJ would check other submissions irrespective of previous slower one. You can check it by submitting to this program a TLE program with for example ( while(1); ) and a second later a correct sumbission -> the second will be checked first. ;-)
@Zoltán Zámbori - How slow? ;-> (approximately of course)

Last edit: 2010-04-27 16:13:46
2010-04-27 06:50:13 Zoltán Zámbori
I think the shortest possible solution in Perl is build on this regexp: (1x$i)!~/^(11+)\1+$/ It is extremely short and of course extremely slow. It is not a problem for me if the time limit close out this code.
2010-04-27 06:05:06 :(){ :|: & };:

You may check the scores now :-)

Also it is not necessary that O(n^2) algorithm need that much of run-time.

If you have given me about 100 secs I could write much shorter code,but that will just waste of SPOJ resources,since any infinite loop or some other bug will unnecessarily use the judge and make other contestants wait ;-)


Last edit: 2010-04-27 06:30:00
2010-04-26 22:34:06 Piotr KÄ…kol
challenger's is using (as You can see from his time) O(n2) algorithm.
We'll see who will have shorter code. ;-)
Elegant? In my opinion it doesn't matter in this kind of tasks. ;-)
2010-04-26 22:28:23 :(){ :|: & };:

Don't know how others are solving this but for me Sieve is giving more shorten + elegant solution for this task.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.