Finding the 10001st prime

Sometimes, when your code is very slow, you just need a new algorithm. SuperBiasedMan's solution makes many good improvements on your code (taking it from 12.4s on my box -- after removing the unnecessary prints -- to just 5.4s). But we can do better. The issue is, we're still checking every odd number in a row and basically learning nothing from all our previous work. The Sieve of Eratosthenes is a very fast algorithm for computing a large number of primes. The idea is simple: we start with all numbers initially as prime candidates, and we iterate through them. If we find a number still marked prime, we mark all of its multiples as not prime. Repeat until done.

The only issue is that we need to store things in memory. For 10,000 primes though, that's not so bad. There's a well known estimate for the number of primes: p_n ~ n log(n). It's a very good estimate such that the ratio is pretty close to 1, so we can start with twice as much memory for good measure:

def primes_sieve(n): p_n = int(2 * n * math.log(n)) # over-estimate p_n sieve = [True] * p_n # everything is prime to start count = 0 

Then we start at 2, and start crossing off numbers

 for i in range(2, p_n): if sieve[i]: # still prime? count += 1 # count it! if count == n: # done! return i for j in range(2*i, p_n, i): # cross off all multiples of i sieve[j] = False 

And that's it. This takes 0.1 seconds. The reasoning is that we're taking advantage of past work. Once we know that, for instance, 11 is prime - we don't have to do any more work for 121 or 407 or whatever. They're already crossed off!

The time difference grows as we go up in count. For the 100,001st prime, using a sieve gives you the answer in 0.8s whereas a naive loop takes just under 9 minutes (8:53.5).

Integer division (and that includes the modulo % instruction) is a pretty expensive operation, several times slower than any other arithmetic operation, and you are having to do many of those. It would be nice if you could you a more sieve-like approach, where modulo operations are replaced by stepped iteration.

Of course the issue with a sieve is that you do not know how far out you need to go to find the 10001st prime. So what we need is a sieve-like procedure that allows us to extend an existing prime list. If you are familiar with the sieve of Erathostenes, the following code should not be too hard to understand:

def extend_primes(n, prime_list): if not prime_list: prime_list.append(2) first_in_sieve = prime_list[-1] + 1 sieve = [True] * (n - first_in_sieve + 1) # Sieve all multiples of the known primes for prime in prime_list: start = prime * prime if start < first_in_sieve: # Rounded up integer division * prime start = ((first_in_sieve - 1) // prime + 1) * prime if start > n: break start -= first_in_sieve for idx in range(start, len(sieve), prime): print idx + first_in_sieve sieve[idx] = False # Sieve all multiples of the primes in the sieve for prime, is_prime in enumerate(sieve): if not is_prime: continue prime += first_in_sieve start = prime * prime if start > n: break start -= first_in_sieve for idx in range(start, len(sieve), prime): print idx + first_in_sieve sieve[idx] = False # Extend prime_lsit with new primes prime_list.extend(p + first_in_sieve for p, is_p in enumerate(sieve) if is_p) 

Now that you have a way of extending a prime list, you just need to extend it until it has sufficient items in it. A not too sophisticated way of going about it could be:

def find_nth_prime(n): prime_list = [2] limit = n while len(prime_list) < n: extend_primes(limit, prime_list) limit *= 2 return prime_list[n - 1] 

This produces the correct result in a fraction of a second.

Alternatively, you could use the fact that the prime counting function is bounded from above by the logarithmic integral, and do normal sieving up to that value. But that would take some of the algorithmic fun away from this problem.

One of the reasons your script is slow is that you're building an array:

primes.append(attempt) 

Over time, the array will become quite large and the performance degrades. Since the answer you're looking for is a singular value, why not optimize out the need to have an array:

def is_prime(n): if n < 2: return False i = 2 while (i * i <= n): if n % i == 0: return False i = i + 1 return True def n_prime(n): i = 2 while n > 0: if is_prime(i): n = n - 1 if n == 0: return i i = i + 1 return -1 print n_prime(10001) 

In your routine, you implement is_prime(n) by checking if it's divisible by primes you've found before it. Whereas, I've reduce the complexity by checking to see n is divisible by the integers in 2..sqrt(n). i.e. I'm lazily checking with non-primes as well, but, I've optimize the search by only checking up to sqrt(n).

Then we just iterate call is_prime(i) in a loop until we've encountered n-primes.

For your specific problem, the answer is 104743.

You have an interesting optimization in your code: you use the fact that the first prime number is 2 to skip all tests of this value, and increment each test by 2.

Call this fact out in a comment!

I agree with SuperBiasedMan that it is potentially confusing, and should be called out. One place it is confusing is in the while loop comparison, where you have to write < (n - 1). It's usually easier to read comparisons when the actual number is in the comparison, whether that means changing from a less than to a less than or equal, or changing the initialization as in this example. Add the value to your list by initializing it with primes = [2] or, if you want to be verbose:

primes = [] # Initialize the algorithm with the first prime primes.append[2] # All other primes are not divisible by previous entries in 'primes' collection ...algorithm... 

But, if you do this, every future loop starts out by testing 2, which is a performance hit that you worked around by incrementing by 2. Either start your loop on the second iteration, or don't add it to the list.

Especially in mathematics problems like this, there is always a trade-off between speed and readability. Isolate it from the users of your code, and only optimize when actually necessary, but make it a conscious decision. Usually, business logic is whatever's clearer, and back-end algorithms like this is whatever's fastest.

There are many prime generation algorithms you can use (which is another code review bit of advice: use existing libraries and research!) or you can optimize what you have. For starters, you don't need to check the whole list - just until the factor being tested is greater than or equal to the square root of your current potential prime candidate. 13 will not be a factor of 14, you only need to check up to 3. But is it faster? Square root is expensive on some hardware. Maybe use a square root approxomation. You'll need benchmarks. And now why is there a square root in your prime verification? It will need a comment!