Path: ...!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!.POSTED!not-for-mail
From: Olivier Miakinen <om+news@miakinen.net>
Newsgroups: fr.comp.lang.python
Subject: =?UTF-8?Q?Re:_D=c3=a9composition_d'un_nombre_en_facteurs_premiers.?=
Date: Sat, 25 Mar 2023 13:44:25 +0100
Organization: There's no cabale
Lines: 74
Message-ID: <tvmqb9$crr$1@cabale.usenet-fr.net>
References: <tvmju0$259vr$1@dont-email.me> <tvmkt4$bkd$1@cabale.usenet-fr.net>
NNTP-Posting-Host: 200.89.28.93.rev.sfr.net
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15
Content-Transfer-Encoding: 8bit
X-Trace: cabale.usenet-fr.net 1679748265 13179 93.28.89.200 (25 Mar 2023 12:44:25 GMT)
X-Complaints-To: abuse@usenet-fr.net
NNTP-Posting-Date: Sat, 25 Mar 2023 12:44:25 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.4
In-Reply-To: <tvmkt4$bkd$1@cabale.usenet-fr.net>
Bytes: 3440

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