Finding first n primes? [duplicate]

Question

Possible Duplicate:
Fastest way to list all primes below N in python

Although I already have written a function to find all primes under n (primes(10) -> [2, 3, 5, 7]), I am struggling to find a quick way to find the first n primes. What is the fastest way to do this?

Answer 1

Start with the estimate g(n) = n log n + n log log n*, which estimates the size of the nth prime for n > 5.

Then run a sieve on that estimate. g(n) gives an overestimate, which is okay because we can simply discard the extra primes generated which are larger than the desired n.

Then consider the answers in "Fastest way to list all primes below N in python".

If you are concerned about the actual runtime of the code (instead of the order of magnitude of the time complexity of the algorithm), consider using one of the solutions that use numpy (instead of one of the "pure python" solutions).

*When I write log I mean the natural logarithm.

Answer 2

According to this, the nth prime number p_n satisfies

p_n < n ln(n) + n ln( ln(n) )

for n >= 6

So if you run your current function (or, e.g., one of the sieves mentioned in other answers) using the next integer greater than the right-hand side above, you are guaranteed to find the nth prime.