[O365] Décomposition d'un nombre en facteurs premiers

Bonjour à tous,

Suite à une question sur ce fil, je me suis dit qu'il serait intéressant d'étudier la décomposition en facteurs premiers d'un nombre sur Excel avec les nouvelles fonctions dynamiques disponibles sur l'abonnement 365.

J'ai écrit une formule qui permet de réaliser la décomposition d'un nombre en facteurs premiers jusqu'à des nombres assez importants (testé jusqu'à 2^21-1 = 2 097 151 qui semble être un ordre de grandeur limite pour le calcul).

On va donc chercher la décomposition d'un entier positif (N*) en facteurs premiers.

[CI-APRÈS EXPLICATIONS DE LA FORMULE] >> Formule finale en bas de ce post

Vérification qu'un entier k est premier

Pour cela, on a besoin de savoir si un entier k est premier. Une manière de faire est de vérifier si, de tous les entiers entre 2 et √k (arrondi), aucun ne divise k. Alors k est premier.

Autrefois on pouvait faire cette vérification avec la formule

=SI(ENT(A1)=2;"Premier";SI(ET(MOD(ENT(A1);LIGNE(DECALER($A$2;;;ARRONDI.SUP(RACINE(ENT(B2));0)-1)))<>0);"Premier";"Non Premier"))

Sur O365, on peut simplifier cette formule par

LAMBDA(n; OU(n<=3; ET(MOD(n; SEQUENCE(ARRONDI.SUP(RACINE(n); 0); ; 2))<>0)))

Et en donnant un nombre (n) au lambda, on retrouve VRAI ou FAUX selon qu'il soit premier ou non.

On utilisera ce lambda en l'appelant isPrime dans le LET général.

Génération de la liste des diviseurs de k

Les diviseurs de k sont compris entre 1 et k/2. On va sauter 1 puisqu'il ne nous intéresse pas dans ce cas précis. On va donc créer une séquence de 2 à k/2, puis on va vérifier pour tous s'ils divisent k ou non. Si oui, on les garde. On utilise MOD pour vérifier ce critère.

EXCLURE(REDUCE(1; SEQUENCE(ARRONDI.SUP(k/2; 0); ; 2); LAMBDA(acc; v; SI(MOD(k; v)=0; ASSEMB.V(acc; v); acc))); 1)

On utilise EXCLURE pour retirer le 1 de la liste (techniquement, on a besoin d'une valeur d'initialisation de la liste, c'est ce 1), et REDUCE pour faire le tri de cette liste.

On utilisera ce résultat en l'appelant divisors dans le LET général.

Extraction des diviseurs premiers de k

On reprend la liste des diviseurs, et on y applique un second filtre, pour ne récupérer que les diviseurs qui sont premiers.

REDUCE(; divisors; LAMBDA(acc; v; SI(isPrime(v); ASSEMB.V(acc; v); acc)))

On utilisera ce résultat en l'appelant primeFact dans le LET général.

Calcul des puissances

Maintenant que nous avons la liste des diviseurs premiers de k, nous savons que k s'écrit sous la forme

K = d1^p1 * d2^p2 * …

Avec di les diviseurs premiers de k, et pi leurs puissances respectives.

Pour trouver chaque puissance, il faut itérer : tant que k est divisible par d^p, augmenter p de 1 et recommencer…

Malheureusement on ne peut pas itérer à l'infini pour trouver p, donc on va mettre une limite maximale qui va définir "jusqu'où" notre itération se poursuit. Bon dans les faits on voit que 2^21 est supérieur à 2 millions... donc prendre une valeur autour de 20 offre une grande marge de sécurité.

Pour les puristes, ou pourrait calculer à partir du plus petit facteur premier (d1) le logarithme népérien pour récupérer ce p max, avec le rapport LN(k)/LN(d1)… mais bon… C'est pas super utile.

Si jamais, la formulepMax;ARRONDI.SUP(LN(nb)/LN(INDEX(primeFact;1));0)

Dans la formule finale, j'ai choisi pMax = 25.

Bon, on va donc assigner à chacun des diviseurs di de k leur puissance maximale respective. Pour cela on utilise MAP

MAP(primeFact; LAMBDA(d; MAX(SEQUENCE(pMax)*(MOD(k; d^SEQUENCE(pMax))=0))))

On utilisera ce résultat en l'appelant powers dans le LET général.

Voilà !

On a trouvé la liste des diviseurs premiers de k, et leurs puissances respectives. Maintenant il reste juste à faire de la mise en forme. Deux approches possibles : Un tableau, ou une chaine de caractères.

Il faudra faire un dernier test, si k est premier, alors tous nos calculs ci-dessus vont planter, on appellera donc isPrime sur k pour le tester, et auquel cas on affiche 1*k.

• Approche tableau :

ASSEMB.V(ASSEMB.H("diviseur"; "puissance"); SI(isPrime(k); ASSEMB.H(k; 1); ASSEMB.H(primeFact; powers)))

• Approche chaine de caractères (celle par défaut) :

SI(isPrime(k); k; JOINDRE.TEXTE(" * "; VRAI; BYLIGNE(ASSEMB.H(primeFact; powers); LAMBDA(r; JOINDRE.TEXTE("^"; VRAI; r)))))

Formule complète

Pour traiter la cellule A1, en retournant une chaine de caractères.

=LET(
  DecomposerFact; LAMBDA(k;
    LET(
      isPrime; LAMBDA(n; OU(n<=3; ET(MOD(n; SEQUENCE(ARRONDI.SUP(RACINE(n); 0); ; 2))<>0)));
      divisors; EXCLURE(REDUCE(1; SEQUENCE(ARRONDI.SUP(k/2; 0); ; 2); LAMBDA(acc;v; SI(MOD(k; v)=0; ASSEMB.V(acc; v); acc))); 1);
      primeFact; REDUCE(; divisors; LAMBDA(acc;v; SI(isPrime(v); ASSEMB.V(acc; v); acc)));
      pMax; 25;
      powers; MAP(primeFact; LAMBDA(d; MAX(SEQUENCE(pMax)*(MOD(k; d^SEQUENCE(pMax))=0))));
      resultats; "-----------------------------------------------------------";
      SI(isPrime(k); k; JOINDRE.TEXTE(" * "; VRAI; BYLIGNE(ASSEMB.H(primeFact; powers); LAMBDA(r; JOINDRE.TEXTE("^"; VRAI; r)))))
    )
  ); DecomposerFact(A1)
)

Petit fichier d'exemple :