Nombre de zéros de n factoriel ; n petit⚓︎

On rappelle que, pour \(n\) un entier naturel, la factorielle de \(n\) se note \(n!\) et se définit comme le produit des entiers de \(1\) à \(n\).

\(0! = 1\), comme un produit vide.
\(1! = 1\)
\(2! = 1×2 = 2\)
\(3! = 1×2×3 = 6\)
\(11! = 1×2×3×4×5×6×7×8×9×10×11 = 39916800\)
\(42! = 1405006117752879898543142606244511569936384000000000\)

On constate que

\(3!\) se termine par aucun zéro.
\(11!\) se termine par 2 zéros.
\(42!\) se termine par 9 zéros.

Construire un tableau de longueur 1000, tel que nb_zeros_factorielle[n] contient le nombre de zéros dans l'écriture décimale de \(n!\), pour \(n\) entier inférieur à \(1000\).

Exemples

🐍 Console Python

>>> nb_zeros_factorielle[3]
0
>>> nb_zeros_factorielle[11]
2
>>> nb_zeros_factorielle[42]
9
>>> len(nb_zeros_factorielle) >= 1000
True

###

# testsbksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[3] == 0bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[11] == 2bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[42] == 9bksl-nlbksl-nlassert len(nbpy-undzerospy-undfactorielle) >= 1000bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlNBpy-undZEROS = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 37, 37, 37, 37, 37, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 47, 47, 47, 47, 47, 49, 49, 49, 49, 49, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 68, 68, 68, 68, 68, 69, 69, 69, 69, 69, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 74, 74, 74, 74, 74, 75, 75, 75, 75, 75, 76, 76, 76, 76, 76, 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 82, 82, 82, 82, 82, 83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 86, 86, 86, 86, 86, 87, 87, 87, 87, 87, 88, 88, 88, 88, 88, 89, 89, 89, 89, 89, 90, 90, 90, 90, 90, 93, 93, 93, 93, 93, 94, 94, 94, 94, 94, 95, 95, 95, 95, 95, 96, 96, 96, 96, 96, 97, 97, 97, 97, 97, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 101, 101, 101, 101, 101, 102, 102, 102, 102, 102, 103, 103, 103, 103, 103, 105, 105, 105, 105, 105, 106, 106, 106, 106, 106, 107, 107, 107, 107, 107, 108, 108, 108, 108, 108, 109, 109, 109, 109, 109, 111, 111, 111, 111, 111, 112, 112, 112, 112, 112, 113, 113, 113, 113, 113, 114, 114, 114, 114, 114, 115, 115, 115, 115, 115, 117, 117, 117, 117, 117, 118, 118, 118, 118, 118, 119, 119, 119, 119, 119, 120, 120, 120, 120, 120, 121, 121, 121, 121, 121, 124, 124, 124, 124, 124, 125, 125, 125, 125, 125, 126, 126, 126, 126, 126, 127, 127, 127, 127, 127, 128, 128, 128, 128, 128, 130, 130, 130, 130, 130, 131, 131, 131, 131, 131, 132, 132, 132, 132, 132, 133, 133, 133, 133, 133, 134, 134, 134, 134, 134, 136, 136, 136, 136, 136, 137, 137, 137, 137, 137, 138, 138, 138, 138, 138, 139, 139, 139, 139, 139, 140, 140, 140, 140, 140, 142, 142, 142, 142, 142, 143, 143, 143, 143, 143, 144, 144, 144, 144, 144, 145, 145, 145, 145, 145, 146, 146, 146, 146, 146, 148, 148, 148, 148, 148, 149, 149, 149, 149, 149, 150, 150, 150, 150, 150, 151, 151, 151, 151, 151, 152, 152, 152, 152, 152, 156, 156, 156, 156, 156, 157, 157, 157, 157, 157, 158, 158, 158, 158, 158, 159, 159, 159, 159, 159, 160, 160, 160, 160, 160, 162, 162, 162, 162, 162, 163, 163, 163, 163, 163, 164, 164, 164, 164, 164, 165, 165, 165, 165, 165, 166, 166, 166, 166, 166, 168, 168, 168, 168, 168, 169, 169, 169, 169, 169, 170, 170, 170, 170, 170, 171, 171, 171, 171, 171, 172, 172, 172, 172, 172, 174, 174, 174, 174, 174, 175, 175, 175, 175, 175, 176, 176, 176, 176, 176, 177, 177, 177, 177, 177, 178, 178, 178, 178, 178, 180, 180, 180, 180, 180, 181, 181, 181, 181, 181, 182, 182, 182, 182, 182, 183, 183, 183, 183, 183, 184, 184, 184, 184, 184, 187, 187, 187, 187, 187, 188, 188, 188, 188, 188, 189, 189, 189, 189, 189, 190, 190, 190, 190, 190, 191, 191, 191, 191, 191, 193, 193, 193, 193, 193, 194, 194, 194, 194, 194, 195, 195, 195, 195, 195, 196, 196, 196, 196, 196, 197, 197, 197, 197, 197, 199, 199, 199, 199, 199, 200, 200, 200, 200, 200, 201, 201, 201, 201, 201, 202, 202, 202, 202, 202, 203, 203, 203, 203, 203, 205, 205, 205, 205, 205, 206, 206, 206, 206, 206, 207, 207, 207, 207, 207, 208, 208, 208, 208, 208, 209, 209, 209, 209, 209, 211, 211, 211, 211, 211, 212, 212, 212, 212, 212, 213, 213, 213, 213, 213, 214, 214, 214, 214, 214, 215, 215, 215, 215, 215, 218, 218, 218, 218, 218, 219, 219, 219, 219, 219, 220, 220, 220, 220, 220, 221, 221, 221, 221, 221, 222, 222, 222, 222, 222, 224, 224, 224, 224, 224, 225, 225, 225, 225, 225, 226, 226, 226, 226, 226, 227, 227, 227, 227, 227, 228, 228, 228, 228, 228, 230, 230, 230, 230, 230, 231, 231, 231, 231, 231, 232, 232, 232, 232, 232, 233, 233, 233, 233, 233, 234, 234, 234, 234, 234, 236, 236, 236, 236, 236, 237, 237, 237, 237, 237, 238, 238, 238, 238, 238, 239, 239, 239, 239, 239, 240, 240, 240, 240, 240, 242, 242, 242, 242, 242, 243, 243, 243, 243, 243, 244, 244, 244, 244, 244, 245, 245, 245, 245, 245, 246, 246, 246, 246, 246]bksl-nlbksl-nlfor n, attendu in enumerate(NBpy-undZEROS):bksl-nl assert nbpy-undzerospy-undfactorielle[n] == attendu, f"Erreur avec n = {n}"bksl-nlbksl-nl ∞/∞

nbpy-undzerospy-undfactorielle = [...]bksl-nl...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[3] == 0bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[11] == 2bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[42] == 9bksl-nlbksl-nlassert len(nbpy-undzerospy-undfactorielle) >= 1000bksl-nlbksl-nlnbpy-undzerospy-undfactorielle = [0]bksl-nlbksl-nldef nbpy-undzeros(n):bksl-nl resultat = 0bksl-nl while n % 10 == 0:bksl-nl n //= 10bksl-nl resultat += 1bksl-nl return resultatbksl-nlbksl-nlfactorielle = 1bksl-nlfor n in range(1, 1000):bksl-nl factorielle py-str= nbksl-nl suivant = nbpy-undzeros(factorielle)bksl-nl nbpy-undzerospy-undfactorielle.append(suivant)bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[3] == 0bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[11] == 2bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[42] == 9bksl-nlbksl-nlassert len(nbpy-undzerospy-undfactorielle) >= 1000bksl-nlbksl-nl

Ici, on appelle la fonction nb_zeros sur un nombre factoriel qui est très grand.

Version efficace⚓︎

🐍 Script Python

def nb_facteurs_5(n):
    resultat = 0
    while n % 5 == 0:
        n //= 5
        resultat += 1
    return resultat

nb_zeros_factorielle = [0]

for n in range(1, 1000):
    apport = nb_facteurs_5(n)
    suivant = nb_zeros_factorielle[n-1] + apport
    nb_zeros_factorielle.append(suivant)

Cette version ressemble beaucoup à la précédente ; presque la même fonction.

La différence essentielle est qu'ici nb_facteurs est appelé avec un nombre petit en paramètre.

À méditer. Cette différence subtile est très importante. Ici, on gagne sérieusement en efficacité grâce à la taille réduite du paramètre dont le cout est plus faible à traiter.

Indice 1

Pour une version facile, on pourra utiliser une fonction qui renvoie le nombre de zéros d'un entier, on passera en argument la factorielle d'un entier.

Après avoir réussi. Tenter une version efficace avec l'indice 2.

Indice 2

Pour une version efficace, on cherchera à calculer l'augmentation du nombre de zéros, d'une factorielle à une autre, en fonction du nouveau facteur. Il s'agit du nombre de fois que l'on peut diviser par 5 ce nouveau facteur.