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

Le 25/03/2023 12:11, je répondais à Dominique :

 
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.

J'ai fait exactement ça. Après avoir testé la division par 2 et par 3 je
ne teste plus que les divisions par 6k-1 et 6k+1. Après l'affichage des
facteurs premiers j'ai aussi ajouté l'affichage de tous les diviseurs,
mais je ne suis pas sûr que mon code soit optimal. Merci de me dire si
je peux faire mieux.

Le code :
=========================================================================
# Pour un nombre entier, retourne sa décomposition en facteurs premiers
def facteurs(nb):
    liste = []
    if nb <= 1:
        return liste
    while nb % 2 == 0:  # diviseur 2
        liste.append(2)
        nb /= 2
    while nb % 3 == 0:  # diviseur 3
        liste.append(3)
        nb /= 3
    cpt = 5
    while nb > 1:
        while nb % cpt == 0: # diviseurs du type 6k-1 (5, 11, 17, ...)
            liste.append(cpt)
            nb /= cpt
        cpt += 2    # 6k-1 -> 6k+1
        while nb % cpt == 0: # diviseurs du type 6k+1 (7, 13, 19, ...)
            liste.append(cpt)
            nb /= cpt
        cpt += 4    # 6k+1 -> 6k+5 i.e. 6k'-1
    return liste

# À partir de la décomposition en facteurs premiers, retourne la liste
# des diviseurs du nombre
def diviseurs(facteurs):
    liste = [1]
    for facteur in facteurs:
        liste += [facteur * nb for nb in liste]
    return sorted(set(liste))

nb = int(input('Nombre : '))

while nb > 1:
    liste = facteurs(nb)
    print(f'Facteurs premiers de {nb} : {liste}')
    liste = diviseurs(liste)
    print(f'Diviseurs de {nb} : {liste}')

    nb = int(input('Nombre : '))
=========================================================================

Exemple d'exécution :
=========================================================================
om@kentia:~/tmp$ python3 decompose.py
Nombre : 12
Facteurs premiers de 12 : [2, 2, 3]
Diviseurs de 12 : [1, 2, 3, 4, 6, 12]
Nombre : 18
Facteurs premiers de 18 : [2, 3, 3]
Diviseurs de 18 : [1, 2, 3, 6, 9, 18]
Nombre : 1001
Facteurs premiers de 1001 : [7, 11, 13]
Diviseurs de 1001 : [1, 7, 11, 13, 77, 91, 143, 1001]
Nombre : 0
=========================================================================


--
Olivier Miakinen