# 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.