#Project Euler 7:
#What is the 10,001st prime number?
#Runtime, iteration setup:
import time
start = time.time()
from math import log
from math import sqrt
bigO = 0
#Init
nth = 10001
nmax = int(nth*(log(nth)+log(log(nth))))
nlist = list(range(3,nmax,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
#3) Repeat for the first sqrt(nmax) primes
# The remaining numbers should be prime since all shared factors have been removed
#4) Append the remaining primes to the first set
primes.append(2)
while len(primes) <= int(sqrt(nmax))+1:
p = nlist[0]
primes.append(p)
for n in nlist:
if n%p == 0:
nlist.remove(n)
bigO += 1
primes.extend(nlist)
#Output
runtime = str((time.time()-start)*1000)
print("Number of primes found: ",len(primes))
print("Prime(",nth,"): ",primes[nth-1])
print("#--- Run Stats ---#")
print("Iterations: ",bigO)
print("Total elapsed time: " + runtime + " milliseconds.")