3
\$\begingroup\$

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 :)

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.