codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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."
Private
[
?
]
Run code
Submit