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

Liste des GroupesRevenir à fcl python 
Sujet : Re: Décomposition d'un nombre en facteurs premiers.
De : om+news (at) *nospam* miakinen.net (Olivier Miakinen)
Groupes : fr.comp.lang.python
Date : 25. Mar 2023, 14:44:25
Autres entêtes
Organisation : There's no cabale
Message-ID : <tvmqb9$crr$1@cabale.usenet-fr.net>
References : 1 2
User-Agent : Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.4
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

Date Sujet#  Auteur
25 Mar 23 * Décomposition d'un nombre en facteurs premiers.14Dominique
25 Mar 23 +* Re: Décomposition d'un nombre en facteurs premiers.3Olivier Miakinen
25 Mar 23 i`* Re: Décomposition d'un nombre en facteurs premiers.2Olivier Miakinen
25 Mar 23 i `- Re: Décomposition d'un nombre en facteurs premiers.1michel
25 Mar 23 +- Re: Décomposition d'un nombre en facteurs premiers.1Olivier Miakinen
25 Mar 23 +- Re: Décomposition d'un nombre en facteurs premiers.1Olivier Miakinen
25 Mar 23 `* Re: Décomposition d'un nombre en facteurs premiers.8michel
25 Mar 23  `* Re: Décomposition d'un nombre en facteurs premiers.7Olivier Miakinen
25 Mar 23   +* Re: Décomposition d'un nombre en facteurs premiers.2michel
26 Mar 23   i`- Re: Décomposition d'un nombre en facteurs premiers.1Dominique
26 Mar 23   `* Re: Décomposition d'un nombre en facteurs premiers.4Dominique
26 Mar 23    +- Re: Décomposition d'un nombre en facteurs premiers.1Olivier Miakinen
26 Mar 23    `* Re: Décomposition d'un nombre en facteurs premiers.2Olivier Miakinen
26 Mar 23     `- Re: Décomposition d'un nombre en facteurs premiers.1Dominique

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal