Take the 2-minute tour ×

I'm looking for a fast solution to generate all first n prime numbers

Is it faster to use 6m +/- 1 formula or the sieve of Eratosthenes to generate prime numbers or there is a faster solution?.

n <= 1e6

Thanks in advance.

share|improve this question

closed as off topic by Fosco, Chris Farmer, ildjarn, svick, KP. May 27 '11 at 19:46


3 Answers 3

The Sieve of Atkin is generally preferred over the Sieve of Eratosthenes.

share|improve this answer

For the first n prime numbers you should use the Sieve of Eratosthenes. If n is only 1 million it should be plenty fast enough.

Other sieves such as the Sieve of Atkin may be asymptotically faster but are usually slower for realistic sizes.

share|improve this answer

It is faster to use the sieve of Eratosthenes. However, you'll need to figure out an upper bound on how far to generate, which can be done by #primes ~ n/ln(n). Include a sufficient buffer.

share|improve this answer
