Project Euler 005

#-*-coding:utf-8-*-
#filename:ProjectEuler005.py
"""
2520 is the smallest number that can be divided by each of the numbers
from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible
by all of the numbers from 1 to 20?
"""
"""
# ugly solution:
def is_even_divisible(m, n=10):
    for i in range(2, n+1):
        if m % i != 0:
            return False
    return True
def smallest_num(n):
    m = n
    while not is_even_divisible(m, n):
        m = m + 1
    return m
if __name__ == '__main__':
    for i in range(1, 21):
        print i, smallest_num(i)
"""
# better one:
from math import sqrt, log
def is_prime(n):
    for i in range(2, int(sqrt(n))+1):
        if n % i == 0:
            return False
    return True
def smallest_num(n):
    k = n
    N = 1
    # primes smaller than k
    p = [i for i in range(2, k+1) if is_prime(i)]
    up = []
    # primes are factors of N, but some mutiplys more than once, like: N = p1**2 * p2*3 *...
    for i in range(len(p)):
        if p[i] * p[i] < k:
            # p^n < k, n < log(k) / log(p)
            up.append(int(log(k) / log(p[i])))
        else:
            up.append(1)
        N = N * p[i]**up[i]
    return N
if __name__ == '__main__':
    for i in range(1, 30):
        print i, smallest_num(i)