4

19/06/22

On continue avec le projet Euler. Le probleme 5 nous propose de jouer avec des multiples communs :

Ennoncé

\(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\)?

On pourrait tout de suite donner un multiple des nombres de \(1\) a \(20\) :

\[ n = 1 \times 2 \times \ldots \times 19 \times 20 = 2432902008176640000 \]

Mais il ne s'agit pas la du plus petit multiple de ces nombres. Nous allons voir comment determiner si un nombre est un multiple d'un autre.

Multiplicite

Oui la question peut sembler triviale, mais elle est essentielle pour comprendre le probleme. Comment savoir si un nombre est multiple d'un autre ?

Il faut passer par la division euclidienne des deux termes et regarder le reste de cette division, s'il vaut \(0\) le diviseur est multiple du quotien.

\[ \text{Si} \ n \equiv 0 [x] \ \text{alors} \ x \ \text{est multiple de} \ n \]

Trouver le plus petit multiple commun

Il doit exister une astuce mathematique pour le calculer, mais avec mes connaissances actuelles je vais simplement utiliser la programmation pour resoudre ce probleme :

# x est la solution cherchee
x = 1

# Boucle infinie
while True:
    # modulus est une variable que j'utilise pour savoir si x est un multiple de n
    modulus = True
    # Iteration des 20 premiers entiers (1)
    for n in range(1, 20):
        # Teste si x est multiple ou non
        if x % n != 0:
            # Si x n'est pas multiple, on passe a l'iteration suivante de la
            # boucle
            # Pas besoin de tester les entiers restants
            modulus = False
            break
    # Si modulus est vrai a ce moment, cela signifie que x est bien un multiple
    # des nombres de 1 a 20
    if modulus == True:
        # Affichage de x
        print(x)
        break

    # Si modulus est faux, x n'est pas un multiple des nombres de 1 a 20, on
    # l'incremente et on recommance la boucle
    x += 1

# 232792560

1. Note : j'aurai tout aussi bien pu tester chaque entier manuellement, j'ai optimise la lecture du code et son adaptativite. En effet on peut simplement changer \(20\) pour changer les multiples communs.

Le programme trouve \(232792560\) comme solution. Il s'agit bien de l'entier le plus petit multiple des nombres de \(1\) a \(20\).