Voici un résumé de l'énoncé du problème 5 "Smallest multiple" du Project Euler (traduction complète en français ici) :

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20 ?

Compréhension du problème

Reformulons le problème : il nous faut trouver le plus petit entier divisible par tous les nombres de 1 à 20.

La première idée de résolution serait de faire un programme qui teste pour chacun des nombres à partir de 20 si ils sont divisibles par les nombres de 1 à 20. Le problème est que le temps d'exécution d'un tel programme pour trouver la réponse est très grand (vous pouvez vérifier). Par conséquent, il nous faut réfléchir à une autre façon de résoudre ce problème.

En fait, ce problème est soluble en n'utilisant que des mathématiques car trouver le plus petit nombre divisible par les nombres de 1 à 20 revient à calculer le PPCM des nombres de 1 à 20.

Pour ce faire, il nous faut décomposer en produits de facteurs premiers les nombres de 1 à 20, ce qui donne :

$$\begin{align}&4 = 2^2 \qquad 6 = 2\cdot 3 \qquad 8 = 2^3 \qquad 9 = 3^2 \qquad 10 = 2\cdot 5 \qquad 12 = 2^2 \cdot 3 \\ & 14 = 2\cdot 7 \qquad 15 = 3 \cdot 5 \qquad 16 = 2^4 \qquad 18 = 2\cdot 9 \qquad 20 = 2^2 \cdot 5 \end{align}$$

Les autres nombres étant premiers. Et calculer le PPCM à l'aide de cette décomposition en facteurs premiers :

$$\text{PPCM}(1, 2, ..., 19, 20) = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19$$

Le programme

Pour résoudre ce problème, une simple calculatrice est nécessaire, mais si vous n'en avez pas sous la main et que vous voulez utiliser Python, voici ce que l'on peut utiliser :

print(2*2*2*2*3*3*5*7*11*13*17*19)

Le résultat

La réponse à ce problème est 232792560.