Any better way to solve Project Euler problem # 5

Question

So, here's my attempt on Problem # 5 of Project Euler, which is looking quite clumpsy when seen first time. Is there any better way to solve this? Or any built-in library that already does some part of the problem?

Code: -

'''
    Problem 5: 
    2520 is the smallest number that can be divided by each of the numbers from 1 to 10

    What is the smallest number, that is evenly divisible by each of the numbers from
    1 to 20?
'''

from collections import defaultdict

def smallest_number_divisible(start, end):    
    '''
        Function that calculates LCM of all the numbers from start to end
        It breaks each number into it's prime factorization, 
        simultaneously keeping track of highest power of each prime number
    '''
    # Dictionary to store highest power of each prime number.
    prime_power = defaultdict(int)

    for num in xrange(start, end + 1):
        # Prime number generator to generate all primes till num
        prime_gen = (each_num for each_num in range(2, num + 1) if is_prime(each_num))

        # Iterate over all the prime numbers
        for prime in prime_gen:
            # initially quotient should be 0 for this prime numbers
            # Will be increased, if the num is divisible by the current prime
            quotient = 0

            # Iterate until num is still divisible by current prime
            while num % prime == 0:
                num = num / prime
                quotient += 1

            # If quotient of this priime in dictionary is less than new quotient,
            # update dictionary with new quotient
            if prime_power[prime] < quotient:
                prime_power[prime] = quotient

    # Time to get product of each prime raised to corresponding power  
    product = 1

    # Get each prime number with power
    for prime, power in prime_power.iteritems():
        product *= prime ** power

    return product 


def is_prime(num):
    '''
        Function that takes a `number` and checks whether it's prime or not
        Returns False if not prime
        Returns True if prime
    '''
    for i in xrange(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True


if __name__ == '__main__':
    print smallest_number_divisible(1, 20)

    import timeit
    t = timeit.timeit

    print t('smallest_number_divisible(1, 20)', 
             setup = 'from __main__ import smallest_number_divisible', 
             number = 100)

While I timed the code, and it came out with a somewhat ok result. The output came out to be: -

0.0295362259729  # average 0.03

Any inputs?

Answer 1

You are recomputing the list of prime numbers for each iteration. Do it just once and reuse it. There are also better ways of computing them other than trial division, the sieve of Erathostenes is very simple yet effective, and will get you a long way in Project Euler. Also, the factors of n are all smaller than n**0.5, so you can break out earlier from your checks.

So add this before the num for loop:

prime_numbers = list_of_primes(int(end**0.5))

And replace prime_gen with :

prime_gen =(each_prime for each_prime in prime_numbers if each_prime <= int(num**0.5))

The list_of_primes function could be like this using trial division :

def list_of_primes(n)
    """Returns a list of all the primes below n"""
    ret = []
    for j in xrange(2, n + 1) :
        for k in xrange(2, int(j**0.5) + 1) :
            if j % k == 0 :
                break
        else :
            ret.append(j)
    return ret

But you are better off with a very basic sieve of Erathostenes:

def list_of_primes(n) :
    sieve = [True for j in xrange(2, n + 1)]
    for j in xrange(2, int(sqrt(n)) + 1) :
        i = j - 2
        if sieve[j - 2]:
            for k in range(j * j, n + 1, j) :
                sieve[k - 2] = False
    return [j for j in xrange(2, n + 1) if sieve[j - 2]]

---

There is an alternative, better for most cases, definitely for Project Euler #5, way of going about calculating the least common multiple, using the greatest common divisor and Euclid's algorithm:

def gcd(a, b) :
    while b != 0 :
        a, b = b, a % b
    return a

def lcm(a, b) :
    return a // gcd(a, b) * b

reduce(lcm, xrange(start, end + 1))

On my netbook this gets Project Euler's correct result lightning fast:

In [2]: %timeit reduce(lcm, xrange(1, 21))
10000 loops, best of 3: 69.4 us per loop

Answer 2

You can use the Sieve of Erathosthenes just once AND count the factors while you filter the primes: Java here, so hard to compare, but it can compute the result one million times in under half a second

long start = System.currentTimeMillis();
for (int run = 0; run < 1000000; run++) {
    int n = 20;
    int result = 1;

    boolean[] isPrime = new boolean[n + 1];
    for (int i = 2; i <= n; i++) {
        isPrime[i] = true;
    }

    for (int currentPrime = 2; currentPrime <= n; currentPrime++) {
        if (isPrime[currentPrime]) {
            int maxAmount = 0;
            for (int j = 1; currentPrime * j <= n; j++) {
                isPrime[currentPrime * j] = false;
                int amount = 1;
                int num = j;
                while (num % currentPrime == 0) {
                    num = num / currentPrime;
                    amount++;
                }
                if (amount > maxAmount) {
                    maxAmount = amount;
                }
            }
            for (int j = 1; j <= maxAmount; j++) {
                result *= currentPrime;
            }
        }
    }
}

long end = System.currentTimeMillis();
System.out.println(end - start);

Prints

446 #milliseconds