Finding first n primes?

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?

Not a duplicate: OP wants the first *n* primes, not all primes below *n*. — Cameron Skinner, Feb 06 '11 at 05:37
Duplicate of: http://stackoverflow.com/questions/2897297/speed-up-bitstring-bit-operations-in-python — Russell Dias, Feb 06 '11 at 05:38
There is almost no difference between "finding the first n primes" and "finding all primes below n". Any algorithm that can find all primes below k can easily be modified to continue increasing k until n primes are found. — Olhovsky, Feb 06 '11 at 05:41
@TheBigO: It's not intuitive (at least not to me) how to do that efficiently - for example, wouldn't you need to do a whole lot of extra work in the sieve if you try to increase *n*? From my brief read of the algorithm it feels like you'd have to essentially restart with the new *n*. — Cameron Skinner, Feb 06 '11 at 05:44
@Cameron Skinner, fair enough. I've added an answer to address those concerns. — Olhovsky, Feb 06 '11 at 05:46
This is not a duplicate, it's asking a different question from the proposed duplicate. First n primes vs. all primes below n. — Olhovsky, Feb 06 '11 at 23:51

score 9 · Accepted Answer · edited May 23 '17 at 12:26

9

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.

edited May 23 '17 at 12:26

Community

1
1

answered Feb 06 '11 at 05:35

Olhovsky

5,466
3
36
47

I'm not exactly sure where to go with this... my code `primes(int(pi*n))[:n]` only returns the correct number of primes for numbers bellow 12. – John Howard Feb 06 '11 at 06:31
Your code should run `primes(g(n))`. I'm not sure if that's what you meant. There was an error in the `g(n)` function in my answer, try again using the new function. – Olhovsky Feb 06 '11 at 07:52

score 5 · Answer 2 · answered Feb 06 '11 at 05:49

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.

score 1 · Answer 3 · answered Feb 06 '11 at 05:34

1

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.

answered Feb 06 '11 at 05:34

Phrogz

296,393
112
651
745

1

+1 for getting the name right, -1 for proposing the same (incorrect) solution. – Chris Lutz Feb 06 '11 at 05:36
@ChrisLutz I suppose I deserve it for jumping in with an answer before editing to flesh it out, but it seems reasonable to me (after my edit) to use π to estimate a reasonable overshoot and then just stop early on the way there. I'll have to see what the duplicate answer suggests. :) – Phrogz Feb 06 '11 at 05:38
I haven't done any downvoting in this question. I was being humerous as my math yields a net of zero. – Chris Lutz Feb 06 '11 at 05:48
@ChrisLutz I understand; I've made plenty of similar "no-vote" comments in the past. :) – Phrogz Feb 06 '11 at 05:57

Vicfred · Answer 4 · 2011-02-06T05:51:47.213

0

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.

edited Feb 06 '11 at 05:51

answered Feb 06 '11 at 05:31

Vicfred

318
1
3
9

That's another method for finding primes under n. – Chris Lutz Feb 06 '11 at 05:32
I have seen about 172 primes under n functions, I am looking for a first n primes code. – John Howard Feb 06 '11 at 05:34

score 0 · Answer 5 · answered Feb 06 '11 at 05:42

0

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

answered Feb 06 '11 at 05:42

catchmrbharath

69
1
2
8

Finding first n primes?

5 Answers5

Linked