Problem 7 - Nth Prime

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?

Considering the run time of my original implementation:

# 23.6239449978 seconds

There is a lot to improve on in this:

import math
primes = [2,3,5,7]
itera = 8
while len(primes) < 10001:
    primelength = len(primes)
    for x in xrange(primelength):
        if itera % primes[x] == 0:
            break
        elif primes[x] > int(math.ceil(itera/2)):
            primes.append(itera)
            break
    itera += 1
print primes[-1]

Well, one thing to notice immediately is the iterator that only increments by one. Let's cut it in half.

primes = [2,3,5]
itera = 7
while len(primes) < 10001:
    primelength = len(primes)
    for x in xrange(primelength):
        if itera % primes[x] == 0:
            break
        elif primes[x] > int(math.ceil(itera/2)):
            primes.append(itera)
            break
    itera += 2
print primes[-1]

So, how much did that help?

# 23.306112051 seconds

Hmph. That doesn't help much at all.
Well, let's try removing our need to keep a massive list of integers and constantly read and write to it. That should reduce our average iteration time.

lastprime = 0
check = 3
pcount = 2
while pcount <= 10001:
    primeflag = True
        for x in range(3, int(math.ceil(math.floor(check))), 2):
            if check % x == 0:
                primeflag = False
                break
    if primeflag:
        lastprime = check
        pcount += 1
    check += 2
print lastprime

Our running time is:

# 94.41918993

Hmm . . .

Well, we have a relatively inefficient method of checking for primes with a flag. Also, we're checking all of the odd numbers, rather than deliberately stepping over some. Let's implement a more modular means of checking for primes. We can eliminate the two easiest prime factors straight away, as well as the entire category of non-primes below 2.

if x < 2:
    return False
if x == 2:
    return True
if x % 2 == 0:
    return False
if x % 3 == 0:
    return False

With these out of the way, we can put an upper limit on the factors that we check for a specific prime. Since we've already eliminated 2 and 3 as factors, we can say that the largest possible factor of any checked number will be equal to the floor of the square root of that number; One half and one third have already been checked, and any root factors will be larger than these two.

root = math.floor(math.sqrt(x))
factor = 5 # Next prime

Now, we just iterate on a counter, returning false if we find a factor.

while factor <= root:
if x % factor == 0:
    return False
factor += 2

Adding a default return value of True, we finally have a complete function:

def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    if x % 3 == 0:
        return False
    root = math.floor(math.sqrt(x))
    factor = 5
    while factor <= root:
        if x % factor == 0:
            return False
        factor += 2
    return True

From here, we need only iterate over the integers, checking for primes. We can check from the last prime so we don't have to start from the bottom of the integers.

last = 5
diff = 2
primecount = 3
while primecount <= 10000:
 x = last + diff
 if is_prime(x):
  last = x
  diff = 2
  primecount += 1
  continue
 diff += 2
print last

Much better:

# 0.235863924026 seconds