#Project Euler 7:
#What is the 10,001st prime number?

#Runtime, iteration setup:
import time
start = time.time()
from math import log
bigO = 0

#Init
nth = 10001
max = int(nth*(log(nth)+log(log(nth))))
nlist = range(3,max,2)
primes = []

#Sieve for primes (adapted from Euler's Sieve, Sieve of Eratosthenes):
#1) Take the first prime of the list, then remove all elements that are multiples
#2) Move to the next list element and repeat
primes.append(2)
while len(nlist) > 0:
  p = nlist[0]
  primes.append(p)
  for n in nlist:
    if n%p == 0:
      nlist.remove(n)
    bigO += 1

#Output
runtime = str((time.time()-start)*1000)
print "Prime(",nth,"): ", primes[nth]
print "#--- Run Stats ---#"
print "Iterations: ",bigO
print "Total elapsed time: " + runtime + " milliseconds."


  

Timeout