# 007 - 10001st prime

Project Euler problem #7.

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.