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.