Finding the 10001st prime

I'm solving Project Euler problem 7, which says:


By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?

Here's the code I've written:

def primes(n):
    primes = []
    attempt = 3
    while len(primes) < (n-1):
        for i in range(len(primes)):
            if attempt % primes[i] == 0:
                attempt += 2
                break
        else:
            primes.append(attempt)
            print (primes)
    return (primes)

While testing a number, if it finds that the number is divisible by one of the primes in the list, the for loop breaks, and starts again with a larger number. If it isn't divisible, it's added to the list of primes. This keeps going until the list is as large as desired (in this case 10000, and I've omitted 2 so the last member of the list is the 10001st prime)

The problem is that this is extremely slow. I've seen other solutions that can apparently solve this in seconds, if not less. What are some ways I could make this run faster?

First off, don't print every single loop. It's wasteful and surprisingly intensive. Also, you don't need to return all primes, your brief only requires one. You should make it more clear what the function is for. Return the last found prime, probably also rename your function to prime.

Don't omit 2, it's only a strange and confusing work around that you haven't even explained in the code. Just include it in the initialisation of primes.

primes = [2]

Also you don't need to do

for i in range(len(primes)):
    if attempt % primes[i] == 0:

Python has a simpler for var in iterable syntax that lets you get the values directly, which is more efficient.

for i in primes:
    if attempt % i == 0:

But rather than using a for loop at all you can use all. It employs short circuiting and will immediately stop iterating over the loop when it finds any value that has an invalid factor. This is faster than breaking when a prime is found, as primes are much rarer than non primes especially when you get into the high values.

def primes(n):
    primes = [2]
    attempt = 3
    while len(primes) < n:
        if all(attempt % prime != 0 for prime in primes):
            primes.append(attempt)
        attempt += 2
    return primes[-1]

Note, you also forgot to increment attempt when a prime was found. That means that every time you found a prime, it then had to be checked yet again in a very costly way since only the last element in the list would invalidate it.

StackExchange Code Review Q#102507, answer score: 14