# Project Euler: Problem 7
#
# 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 10 001st prime number?
#
#################################
# Solution: 104759
# Best time: 0.03313493728637695
#################################

from time import time

def get_primes(limit):
    '''
        Implementation of Sieve algorithm
        Limit <= 10**8
    '''
    a = [True] * limit
    a[0] = a[1] = False
    for i, isprime in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):
                a[n] = False

start = time()
limit, j = 10001, 2
while True:
    prime = list(get_primes(j))
    if len(prime) >= limit:
        break
    j*=9

elapsed = time() - start
print("Solution: {0} \t Time elapsed: {1}".format(prime[limit], elapsed))