#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."


  

least common multiple:  232792560
#--- Run Stats ---#
Iterations:  32
Total elapsed time: 2.94995307922 milliseconds.