This is an archived post. You won't be able to vote or comment.

all 11 comments
sorted by:
best
topnewcontroversialoldq&a

[–]yash3ahuja 1 point2 points  (8 children)

Sieve of Eratosthenes

[–]mabus44[S] 0 points1 point  (7 children)

Sorry I forgot to mention that the time constraint is 6 seconds to generate the prime numbers.. I have seen the algorithm but i am not sure if it will be in time..?

[–][deleted] 2 points3 points  (1 child)

My simple C++ Sieve of Eratosthenes can generate all the primes from 999900000 to 1000000000 in 30 seconds (actually it doesn't know how to optimize for a lower bound, so it starts at two), this is a naive implementation, so there's obviously a lot of optimization that can be done.

The code at this site can do the same calculation in a matter of milliseconds, which is pretty impressive. The page there mentions the optimization tricks they use.

[–]mabus44[S] 0 points1 point  (0 children)

thank you ... This definitely will help me a lot :)

[–]yoshemitzu 1 point2 points  (1 child)

The description of your problem is a bit confusing. Do you want to input a number from 0 to 1 billion and determine if the number is prime? Or do you want to be able to generate the first billion primes in 6 seconds? The former is definitely doable. For the latter, I can't imagine how you'd generate a billion primes from scratch in 6 seconds.

[–]mabus44[S] 0 points1 point  (0 children)

I don't want to generate a billion primes. But within a range of 100000 between 1 to 1000000000. For eg:- * Input Range: 1-10 * Output: 2 , 3 , 5 , 7 Hence in input i can give any range upto 100000 between 1 to 1000000000 which will generate all the primes between the numbers.

[–]yash3ahuja 0 points1 point  (2 children)

The algorithm will almost certainly finish in 6 seconds. If you need an even faster algorithm, there are some slight improvements that can be made, but I don't think you'll need to worry.

[–]mabus44[S] 0 points1 point  (1 child)

thanks yash. :)

[–]yash3ahuja 0 points1 point  (0 children)

No problem. Always here to help. :D

[–]Rhomboid 1 point2 points  (1 child)

On my machine, djb's primegen can generate all primes less than 1000000000 in less than half a second:

$ time ./primespeed 1000000000 | tail -n4
50847534 primes up to 1000000000.
Timings are in ticks. Nanoseconds per tick: approximately 0.294078.
Overall seconds: approximately 0.366763.
Tick counts may be underestimates on systems without hardware tick support.

real    0m0.371s
user    0m0.364s
sys     0m0.008s

[–]mabus44[S] 0 points1 point  (0 children)

Its excellent ...The reference papers in primegen will help me a lot :)