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.
Submit All submissions Best solutions PDF Back to list

PRIMES - Printing primes

Wersja polska English version

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.

Submit solution!
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
Previous 1  2 Next >
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.