SPOJ.com - Problem PRIMES2

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

Submit solution!

hide comments



	lorem_ipsum_73: 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
	lotus_eater: 2018-12-15 17:39:51 Would someone be kind enough to tell me which topics should I learn to avoid Tle ??
	Michael Kharitonov: 2018-01-02 20:21:47 @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
	Howard Roark: 2017-12-30 16:39:39 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.
	VISHAL DEEPAK AWATHARE: 2015-02-24 10:24:01 in hints on to get the crazy speed?
	Krishna Mohan: 2014-12-28 17:16:19 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

Submit solution!

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