TDPRIMES - Printing some primes


The problem statement is really simple. You are to write all primes less than 10^8

Input

There is no input.

Output

To make the problem less output related write out only the 1st, 101st, 201st, ... 1st mod 100.

Example

Input:

Output:
2
547
1229
...
99995257
99996931
99998953

hide comments
leonardo_2002: 2022-01-25 21:00:35

Can Anyone please share the solution in Python. I have tried everything from normal sieve to bitwise sieve ,however bitwise sieve will only reduce the array size from 10^8 to (10^8)/64. What about Time complexity even if you are skipping even numbers then the time complexity will be around (10^8)/2 i.e 5*10^7. I think under the given time constraint, the no. of iteration possible is only 10^6. I also have used Fast I/P O/P method but still nothing happened. Please Help!!

[NG]: This is a site where we code solutions, not share them. Submit as PyPy, although trying to get a better time with PRIME1 first will get you further in long term.

Last edit: 2022-01-25 23:34:53
sk128: 2021-08-02 20:46:29

Simple Sieve will do the job , no optimization required .

Last edit: 2021-08-02 21:40:33
krishp: 2021-07-28 03:14:27

1.13 seconds in JAVA using BitSet & sieve of eratosthenes

geekystriker: 2021-07-17 17:18:35

Simple sieve worked for me

raviyadav144: 2021-06-09 12:05:10

Just use simple sieve , declare a global array of size 10^8 and it goes AC !!

parag_619: 2021-05-24 18:58:28

used vector instead of array, replace cout with printf and endl with \n, TLE will be removed.

dgenxsid: 2021-04-30 18:18:27

Solved using a bitwise sieve.

akashjarvis: 2021-04-14 18:04:40

@ramsaicrony i am also getting the same issue can you help me out

n7hoatt: 2021-04-07 13:18:42

well well

rushi2001: 2021-03-29 13:36:09

It might give tle in your compliler but will work here


Added by:Alfonso² Peterssen
Date:2010-04-06
Time limit:1.325s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32 ASM64 BF CLPS LISP sbcl LISP clisp ERL HASK ICON ICK JS-RHINO LUA NEM NICE OBJC OCAML PHP PIKE PRLG-swi SCALA SCM guile SCM qobi ST SQLITE TCL WHITESPACE
Resource:Thanks to TDuke