Re: Décomposition d'un nombre en facteurs premiers.

Le 25/03/2023 11:54, Dominique a écrit :

 
Pour commencer à résoudre un exercice de la revue Tangente, j'ai écrit
un script qui décompose un nombre nb en tous ses facteurs premiers :
 
[...]
             if nb==cpt:
                 nb=1
             else:
                 nb=nb/cpt

Pourquoi ce « if/else » ?
Si nb == cpt, alors la division de nb par cpt donnera 1.

Ce script aurait-il pu être amélioré ? Je suppose que oui, mais comment ?

Tu peux d'abord avoir en dur une liste des plus petits nombres premiers,
afin de ne tester que les cpt dans cette liste. Par exemple il est inutile
d'essayer de diviser par 4, par 6 ou par 9, alors que tu as déjà traité les
nombres 2 et 3.

Une fois ta liste épuisée, au lieu de faire des cpt+=1, tu peux simplement
faire des cpt+=2 à partir d'un cpt impair.

Tu peux même partir d'un cpt de la forme 6n+1, faire des cpt+=6, et tester
la division par cpt et par (cpt+4). Comme ça tu ne testes plus aucun multiple
de 2 ou de 3. Et cette technique peut s'étendre pour éliminer aussi les
multiples de 5, puis les multiples de 7... même si là ça devient un peu plus
complexe.


--
Olivier Miakinen