#Project Euler 5:
#What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
#Runtime, iteration setup:
import time
start = time.time()
from math import log
bigO = 0
#Init
max = 20
nlist = range(2,max+1)
primes = []
lcm = 1
#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
while len(nlist) > 0:
p = nlist[0]
primes.append(p)
for n in nlist:
if n%p == 0:
nlist.remove(n)
bigO += 1
#Calculate p^(log_p(max)) for each p, store product-wise in lcm
for prime in primes:
lcm = lcm * prime**int(log(max,prime))
#Output
runtime = str((time.time()-start)*1000)
print "least common multiple: ",lcm
print "#--- Run Stats ---#"
print "Iterations: ",bigO
print "Total elapsed time: " + runtime + " milliseconds."