Hackerrank – Project Euler+ #005 – Smallest multiple

Hackerrank – Problem description

The problem description – Hackerrank.


We need to make a prime factorization of number (problem constraints), because some of the numbers are divisors of the other numbers. We reduce unnecessary multiplications and divisions.

We could use Sieve of Eratosthenes to calculate all prime numbers from 2 to N.

Let’s calculate how many times is a prime number in given number. It will look like the following equation:

    \[n = p_1^{m_1}p_2^{m_2}p_3^{m_3} \ldots p_n^{m_n}\]



denotes how many times is a prime


in a given number.

We can calculate


for every number.




are taken from Sieve of Eratosthenes algorithm. Last step is to calculate exponents

    \[m_1 \ldots m_n\]

. We can calculate as:

    \[m_i = \lceil \frac{\log{n}}{\log{p_i}} \rceil\]

and do it for every prime number.

I created solution in:

All solutions are also available on myGitHub profile.


Leave a Reply

Your email address will not be published. Required fields are marked *