Finding first n primes? [duplicate]

This question already has answers here: Closed 12 years ago.

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 p开发者_运维问答rimes. What is the fastest way to do this?

---

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.

---

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.

---

You want the Sieve of Eratosthenes.

Use the π function to estimate what value of n you want to look towards, overshoot slightly, and then use a sieve to compute up to the point you need.

---

Use sieve of Erastothrones using the fact that prime numbers are either of the form 6n+1 or 6n-1 after 2 and 3.This will improve the speed of the program

---

I don't know if it's the fastest but Euler's Sieve seems good.

EDIT

As the other answers is suggesting you can use basic facts on the prime number theorem2. Or you can learn basic algebraic geometry and use elliptic curve primality testing.