euler_problem_7.py

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

import math
import time

def is_prime(n):
    # Check if it's divisible by 2
    if(not(n & 1)):
        return False
    
    # If we've got this far then only a certain subset of numbers are eligible to be prime, which, after 5, is the first 2 of every 3 odd numbers.
    # First let's check if our number is divisible by either 3 or 5.
    if(n % 3 == 0):
        return False
    
    if((str(n)[-1:] == '5') or (str(n)[-1:] == '0')):
        return False
    
    for i in range(1,int(math.floor(n/6)),1):
        if(n % (6 * i - 1) == 0 or n % (6 * i + 1) == 0):
            return False
    
    # If we've got this far then our number must be prime
    return True

def nth_prime(n):
    x = 0
    count = 1
    while(count<=n):
        if(is_prime(2 * x + 1)):
            count+=1
        x+=1
    return int(2 * x + 1)

t = time.time()
print(t)
print(nth_prime(10001)) # Returns 104761 in 39.46 seconds!
f = time.time()
print(f)
print(f - t)