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