007 - 10001st prime

See Problem 7: What is the 10001st prime number?

This solution is fairly simple (and largely stolen from Aaron Gallagher):

def iter_primes ():
   # handle trivial case
   yield 2
   val = 1
   primesq_pairs = []
   while True:
      curr = None
      while (curr is None):
      val += 2
      curr = val
      for prime, square in primesq_pairs:
         if (curr < square):
            break
         if (curr % prime == 0):
            curr = None
            break
         primesq_pairs.append ((curr, curr**2))
      yield curr

primer_gen = iter_primes()
for x in xrange (10001):
   result = primer_gen.next()
print result

Execution time is slow: 0.2s. Some notes:

• The prime function is written as a fairly general iterator / generator for good practice. No doubt more specialised code would run faster. This also means that we have to instantiate the generator primer_gen = ... and call next the requisite number of times, to get the n th answer.
• We use xrange to save the memory that is created in the loop. A while could also be used here. Sometimes Python cries out for a regular, C++ style for loop ...
• Note that 2 is not included in the internal list of primes. This is because we start searching for the primer from an odd number and increase our test value by 2 in every step, ensuring that our test value is never even and we never have to see if it is divisible by 2.

A brief explanation of the algorithm: as we produce primes, each time we store them. Then any putative primes we create are tested against this list. (Anything that isn't a primer can be decomposed into prime factors, i.e. is divisible by a primer.) This approach also avoids the need of many algorithms (see comments in earlier problems0 to generate a static array the length of the final number.