Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > fr.comp.lang.python > #4045
| From | Olivier Miakinen <om+news@miakinen.net> |
|---|---|
| Newsgroups | fr.comp.lang.python |
| Subject | Re: Décomposition d'un nombre en facteurs premiers. |
| Date | 2023-03-25 13:44 +0100 |
| Organization | There's no cabale |
| Message-ID | <tvmqb9$crr$1@cabale.usenet-fr.net> (permalink) |
| References | <tvmju0$259vr$1@dont-email.me> <tvmkt4$bkd$1@cabale.usenet-fr.net> |
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
Back to fr.comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar
Décomposition d'un nombre en facteurs premiers. Dominique <zzz@aol.com> - 2023-03-25 11:54 +0100
Re: Décomposition d'un nombre en facteurs premiers. Olivier Miakinen <om+news@miakinen.net> - 2023-03-25 12:11 +0100
Re: Décomposition d'un nombre en facteurs premiers. Olivier Miakinen <om+news@miakinen.net> - 2023-03-25 13:44 +0100
Re: Décomposition d'un nombre en facteurs premiers. michel@domain.invalid - 2023-03-25 14:10 +0100
Re: Décomposition d'un nombre en facteurs premiers. Olivier Miakinen <om+news@miakinen.net> - 2023-03-25 12:21 +0100
Re: Décomposition d'un nombre en facteurs premiers. Olivier Miakinen <om+news@miakinen.net> - 2023-03-25 12:25 +0100
Re: Décomposition d'un nombre en facteurs premiers. michel@domain.invalid - 2023-03-25 12:28 +0100
Re: Décomposition d'un nombre en facteurs premiers. Olivier Miakinen <om+news@miakinen.net> - 2023-03-25 12:36 +0100
Re: Décomposition d'un nombre en facteurs premiers. michel@domain.invalid - 2023-03-25 13:59 +0100
Re: Décomposition d'un nombre en facteurs premiers. Dominique <zzz@aol.com> - 2023-03-26 04:17 +0200
Re: Décomposition d'un nombre en facteurs premiers. Dominique <zzz@aol.com> - 2023-03-26 04:24 +0200
Re: Décomposition d'un nombre en facteurs premiers. Olivier Miakinen <om+news@miakinen.net> - 2023-03-26 08:18 +0200
Re: Décomposition d'un nombre en facteurs premiers. Olivier Miakinen <om+news@miakinen.net> - 2023-03-26 14:06 +0200
Re: Décomposition d'un nombre en facteurs premiers. Dominique <zzz@aol.com> - 2023-03-26 19:01 +0200
csiph-web