| Submit | All submissions | Best solutions | Back to list |
PRIMES2 - Printing some primes (Hard) |
The problem statement is really simple (the constraints maybe not). You are to write all primes less than 10^9.
Input
There is no input.
Output
To make the problem less output related write out only the 1st, 501st, 1001st, ... 1st mod 500.
Example
Input: Output: 2 3581 7927 ... 999978527 999988747 999999151
| Added by: | Alfonso² Peterssen |
| Date: | 2010-04-09 |
| Time limit: | 2.281s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC |
| Resource: | Thanks to TDuke |
hide comments
|
2020-07-08 10:32:37
Can any one tell me how to optimize Output in Java to get under Time Limit. am already using PrintWriter class for output |
|
|
2018-12-15 17:39:51
Would someone be kind enough to tell me which topics should I learn to avoid Tle ?? |
|
|
2018-01-02 20:21:47 Michael Kharitonov
@Howard Roark: you need to output every 500th prime number, about 100,000 total @VISHAL DEEPAK AWATHARE: I used segmented sieve of Eratosthenes with wheel factorization mudulo 210. Last edit: 2019-05-05 17:59:16 |
|
|
2017-12-30 16:39:39 Howard Roark
This will be a real challenge on Java. All the optimizations will be needed just to get to computation of the list of primes to come in under the time limit, and that's not even counting the time needed for the I/O. The I/O will also require optimizations to reduce the cost of converting all those integers (about 50 million) to base 10 strings. |
|
|
2015-02-24 10:24:01 VISHAL DEEPAK AWATHARE
in hints on to get the crazy speed? |
|
|
2014-12-28 17:16:19 Krishna Mohan
My code is spending all the time trying to output the numbers, if I just comment out the printf statements, It is taking a little over 3s to run, but with the io it is going to about 14s, is there a faster way to print? --(francky)--> This problem is very few IO related. I think if you try to output the sum of all the required primes, you will have TLE too. Just try that ; this task is not IO related at all. If you can print this sum under 3s, then you should get AC very near to 3s too. There's a difference between sieve (ie have a bit set ready) and have an effective list of primes. Hope this answer could help. --(kmwho)--> Thanks for the help, turns out it was some weird problem with my system, I posted here, because I made a program that just spits out ~100k numbers without any calculations and even that was taking more than 10s! Everything is working faster after a reboot though. I am able to solve it in 4s on my system now, though its still no good for PIII I guess Last edit: 2014-12-28 22:20:48 |
RSS