Project Euler - Problem No.5 - Smallest multiple

Question

Here's the problem at hand:

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?

Here's the code Ive written to solve it:

from math import sqrt
def prime_factorization(n: int) -> dict:
 '''
 Returns a dict with the prime factorization of the integer n, where the keys of the dict are the prime numbers
 and the values are the powers in the factorization for the appropriate prime number key.
 :param n: an integer we want to compute he's prime factorization
 '''
 prime_dict = {}
 # dealing with even prime numbers - e.g. 2
 while n % 2 == 0:
 if 2 not in prime_dict:
 prime_dict[2] = 0
 prime_dict[2] += 1
 n = n // 2
 # dealing with odd numbers
 upper_bound = int(sqrt(n))
 for i in range(3,upper_bound+1):
 while n % i == 0:
 if i not in prime_dict:
 prime_dict[i] = 0
 prime_dict[i] += 1
 n = n // i
 # In case n is prime by itself
 if n > 1:
 prime_dict[n] = 1
 return prime_dict
def smallest_dividable_num(n:int) -> int:
 '''
 Returns the smallest integer whose dividable by all the numbers from 1 to n.
 :param n: an integer upper bound which we want to compute the smallest divisable num from 1 to it.
 '''
 prime_dict = {}
 for i in range(1,n+1):
 tmp_dict = prime_factorization(i)
 for k,_ in tmp_dict.items():
 if k not in prime_dict or prime_dict[k] < tmp_dict[k]:
 prime_dict[k] = tmp_dict[k]
 res = 1
 for k,v in prime_dict.items():
 res = res*(k**v)
 return res

And here's a small test case Ive written for this code:

from ProjectEuler.problem5 import smallest_dividable_num
if __name__ == "__main__":
 # The prime factorization is {2**3,3**2,5,7} -> returns 2520
 print(smallest_dividable_num(10))
 # The prime factorization is {2**2,3,5} -> returns 60
 print(smallest_dividable_num(6))
 # The prime factorization is {2**4,3**2,5,7,11,13,17,19} -> returns 232792560
 print(smallest_dividable_num(20))

Let me know your thoughts about my solution. thanks :)

Answer 1

Handling values not in dict in prime_factorization

In 2 places in prime_factorization, we end up performing dictionnary lookup to set the default value 0 when needed.

There are various other ways to do so:

We could use a variable to store the coefficient for the current divisor:

 # dealing with even prime numbers - e.g. 2
 d = 2
 coef = 0
 while n % d == 0:
 coef += 1
 n = n // d
 if coef:
 prime_dict[d] = coef
 # dealing with odd numbers
 for d in range(3, int(sqrt(n))+1):
 coef = 0
 while n % d == 0:
 coef += 1
 n = n // d
 if coef:
 prime_dict[d] = coef

(Note that if coef is not required if we do not mind having 0s in our dictionnary).

An alternative could be to use an appropriate data structure.

import collections
def prime_factorization(n: int) -> dict:
 '''
 Returns a dict with the prime factorization of the integer n, where the keys of the dict are the prime numbers
 and the values are the powers in the factorization for the appropriate prime number key.
 :param n: an integer we want to compute he's prime factorization
 '''
 prime_dict = collections.defaultdict(int)
 # dealing with even prime numbers - e.g. 2
 d = 2
 while n % d == 0:
 prime_dict[d] += 1
 n = n // d
 # dealing with odd numbers
 for d in range(3, int(sqrt(n))+1):
 while n % d == 0:
 prime_dict[d] += 1
 n = n // d

Or a Counter:

import collections
def prime_factorization(n: int) -> dict:
 '''
 Returns a dict with the prime factorization of the integer n, where the keys of the dict are the prime numbers
 and the values are the powers in the factorization for the appropriate prime number key.
 :param n: an integer we want to compute he's prime factorization
 '''
 prime_dict = collections.Counter()
 # dealing with even prime numbers - e.g. 2
 d = 2
 while n % d == 0:
 prime_dict[d] += 1
 n = n // d
 # dealing with odd numbers
 for d in range(3, int(sqrt(n))+1):
 while n % d == 0:
 prime_dict[d] += 1
 n = n // d

However, my preference is to completely split the concerns between the logic generating the prime divisors and the one counting them. Using a generator, we can get something like:

import collections
def yield_prime_factors(n: int):
 '''Yield prime factors.'''
 d = 2
 while n % d == 0:
 yield d
 n = n // d
 # dealing with odd numbers
 for d in range(3, int(sqrt(n))+1):
 while n % d == 0:
 yield d
 n = n // d
 # In case n is prime by itself
 if n > 1:
 yield n
def prime_factorization(n: int) -> dict:
 '''
 Returns a dict with the prime factorization of the integer n, where the keys of the dict are the prime numbers
 and the values are the powers in the factorization for the appropriate prime number key.
 :param n: an integer we want to compute he's prime factorization
 '''
 return collections.Counter(yield_prime_factors(n))

Iterating over keys and values in smallest_dividable_num

You use for k,_ in tmp_dict.items() which dumps the values from the dict and use tmp_dict[k] which gets the values from the dict.

You could as well just write:

 tmp_dict = prime_factorization(i)
 for k, v in tmp_dict.items():
 if k not in prime_dict or prime_dict[k] < v:
 prime_dict[k] = v

which can also be written:

 for k, v in prime_factorization(i).items():
 if k not in prime_dict or prime_dict[k] < v:
 prime_dict[k] = v

Using max and default values

The snippet just above could be written by taking advantage of the Python builtins:

 prime_dict[k] = max(v, prime_dict.get(k, 0))

Using in place operator

You can write things such as:

 n //= d

or

 res *= (k**v)

to avoid repeating the left member of the operand.

A different algorithm

The algorithm is all about computing Least Common Multiple which can be easily computed with the Greatest Common Divisor.

When this is implemented and tests cases are rewritten to ensure benchmark gives relevant timing:

from timeit import default_timer as timer
import functools
def gcd(a, b):
 """Computes gcd for 2 numbers."""
 while b:
 a, b = b, a % b
 return a
def lcm(a, b):
 """Computes lcm for 2 numbers."""
 return a * b // gcd(a, b)
def lcmm(*args):
 """Computes lcm for numbers."""
 return functools.reduce(lcm, args)
def smallest_dividable_num(n:int) -> int:
 '''
 Returns the smallest integer whose dividable by all the numbers from 1 to n.
 :param n: an integer upper bound which we want to compute the smallest divisable num from 1 to it.
 '''
 return lcmm(*range(1, n + 1))
if __name__ == "__main__":
 start = timer()
 for i in range(20):
 assert smallest_dividable_num(10) == 2520
 assert smallest_dividable_num(6) == 60
 assert smallest_dividable_num(20) == 232792560
 for i in range(1, 40):
 smallest_dividable_num(i)
 end = timer()
 print(end - start)