---
layout: post
title: Project Euler - Problem 5
post-order: 005
---

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?

### Solution #1

Let's brute-force it and see what happens. One thing we know: the number we are trying to find **cannot be** smaller than the products of all primes up to $20$. And the reason for that is, the number we are trying to find has to be divisible by $1$ to $20$ and the only way that can be accomplished is if the prime factors (for example $13$) is in that product.


```python
import math
import time

# let's setle "floor" first: the products of all primes from 1 to 20
def primes_up_to(n):
    product = 2

    for candidate_for_prime in range (3,n+1):
        for i in range (2,candidate_for_prime): 
            if (candidate_for_prime % i == 0):
                break
            elif ((candidate_for_prime % i != 0) & (i + 1 == candidate_for_prime)):
                product *= candidate_for_prime
                
    return product

start = time.time()

divisible_up_to = 20
floor = primes_up_to(divisible_up_to)

# the highest we can go is to n! (n factorial)
ceiling = math.factorial(divisible_up_to)

found = False

for ii in range (floor,ceiling):
    for i in range(2,divisible_up_to+1):
        if ii % i != 0:
            break
        elif i == divisible_up_to:
            print (ii)
            elapsed = time.time() - start
            print(elapsed)
            found = True
            break
    
    if found:
        break
```

    232792560
    162.78695583343506


As you may notice, the running time is extremely high (and it will get higher if we choose a greater `divisible_up_to`). We need to find a more efficient way to tacke this problem.

### Solution #2 - Greatest power of primes

The solution for this problem actually requires **no computation**. And the reason for that is, if we find the prime factorization of each number up to 20 and multiply the greatest power of each, we will find the correct solution.

$$
\begin{align}
2 &= 2^1\\
3 &= 3^1\\
4 &= 2^2\\
5 &= 5^1\\
\vdots\\
18 &= 2^1 \cdot 3^2\\
19 &= 19^1\\
20 &= 2^2 \cdot 5^1
\end{align}
$$

We can take advantage of this and build a list with the prime factors and a list with the prime factor's greatest power that shows up from 1 to `divisible_up_to`. After that, we evaluate the first item of the list of primes raised to the first item of the list of powers, multiplied by the second item of the list of primes raised to the second item of the list of powers and so on.

|LISTS|<td colspan=11>|
|----------------|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| list of primes | [ | 2 | 3 | 5 | 7 | 11| 13| 17| 19| ] |
| list of powers | [ |4  | 2 | 1 | 1 | 1 | 1 | 1 | 1 | ] |

Answer = $2^4 \cdot 3^2 \cdot 5^1 \cdot 7^1 \cdot 11^1 \cdot 13^1 \cdot 17^1 \cdot 19^1 = 232792560$


```python
def primes_list(n):
    list_of_primes = [1,2]

    for i in range (3,n+1):
        for ii in range (2,i): 
            if (i % ii == 0):
                break
            elif ((i % ii != 0) & (ii + 1 == i)):
                list_of_primes.append(i)
                
    return list_of_primes

list_of_primes = primes_list(20)
print (list_of_primes)
```

    [1, 2, 3, 5, 7, 11, 13, 17, 19]


Let's build a new list, with the same number of elements, but now filled with zeros. It will receive the greatest power for each prime:


```python
list_of_powers = [1] * len(list_of_primes)
print(list_of_powers)
```

    [1, 1, 1, 1, 1, 1, 1, 1, 1]


Now we need to check what is the greatest power that shows up, for each of the primes, from 1 to 20.


```python
for i in list_of_primes:
    print (i)

# if it's prime, there's no need to check: the power will be 1
# do the prime factorization of all numbers up to 20
```

    1
    2
    3
    5
    7
    11
    13
    17
    19


Placing everything on a single code,


```python

```

The performance of this second algorithm is much better. We can even increase `divisible_up_to` without a substantial compromise on its performance:


```python

```

e7b4d0e636986467eece660f0daf9bf336a7ddc2
ipynb
Jupyter Notebook
_posts/Problem-005.ipynb
bru1987/euler
cc6d308c4aec32efd369861489aa6b8fc392cb9e
MIT
_posts/Problem-005.ipynb
bru1987/euler
cc6d308c4aec32efd369861489aa6b8fc392cb9e
MIT
_posts/Problem-005.ipynb
bru1987/euler
cc6d308c4aec32efd369861489aa6b8fc392cb9e
MIT
2022-02-23T04:25:24.000Z
2022-02-23T04:25:24.000Z
Qwen/Qwen-72B
1. YES
2. YES