Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > fr.comp.lang.python > #4038 > unrolled thread

Décomposition d'un nombre en facteurs premiers.

Back to article view | Back to fr.comp.lang.python

Contents

  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

#4038 — Décomposition d'un nombre en facteurs premiers.

Bonjour,

Pour commencer à résoudre un exercice de la revue Tangente, j'ai écrit 
un script qui décompose un nombre nb en tous ses facteurs premiers :

nb=int(input('Nombre '))
cpt=1
deb=nb
liste=[1]

while nb>1:
     test=False
     cpt+=1
     while test==False:

         if nb%cpt==0:
             liste.append(cpt)
             if nb==cpt:
                 nb=1
             else:
                 nb=nb/cpt
         else:
             test=True

print('Facteurs de ', deb ,' sont ',liste)

Ce script aurait-il pu être amélioré ? Je suppose que oui, mais comment ?

En vous remerciant,

-- 
Dominique
Courriel : dominique point sextant ate orange en France
Esto quod es

[toc] | [next] | [standalone]

#4039

Le 25/03/2023 11:54, Dominique a écrit :
> 
> Pour commencer à résoudre un exercice de la revue Tangente, j'ai écrit 
> un script qui décompose un nombre nb en tous ses facteurs premiers :
> 
> [...]
>              if nb==cpt:
>                  nb=1
>              else:
>                  nb=nb/cpt

Pourquoi ce « if/else » ?
Si nb == cpt, alors la division de nb par cpt donnera 1.

> Ce script aurait-il pu être amélioré ? Je suppose que oui, mais comment ?

Tu peux d'abord avoir en dur une liste des plus petits nombres premiers,
afin de ne tester que les cpt dans cette liste. Par exemple il est inutile
d'essayer de diviser par 4, par 6 ou par 9, alors que tu as déjà traité les
nombres 2 et 3.

Une fois ta liste épuisée, au lieu de faire des cpt+=1, tu peux simplement
faire des cpt+=2 à partir d'un cpt impair.

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. Et cette technique peut s'étendre pour éliminer aussi les
multiples de 5, puis les multiples de 7... même si là ça devient un peu plus
complexe.


-- 
Olivier Miakinen

[toc] | [prev] | [next] | [standalone]

#4045

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

[toc] | [prev] | [next] | [standalone]

#4047

Le 25 mars 2023 Olivier Miakinen a écrit :

> 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.

Pour présenter ça un peu autrement, ça revient à chercher les
nombres premiers qui peuvent être diviseurs et à ne tester qu'eux.
Je ne cherche pas à exclure tous les nombres qui ne sont pas premiers car
ça serait redondant avec le test de division du nombre testé.


'''
Tous les nombres premiers sont de la forme 6*n-1 ou 6*n+1 pour n>0
(mais tous les nombres de cette forme ne sont pas premiers).
Un nombre non premier est forcément divisible par un nombre premier.
Un diviseur d'un nombre est soit lui-même (il est premier) soit un
nombre inférieur à sa racine carrée.
Les nombres premiers (hormis 2 et 5) se terminent tous par 1, 3, 7 ou 9. 
Les nombres 0 et 1 ne sont pas premiers.
'''

from math import sqrt

nb = int(input('Nombre '))
liste = []
premiers = [2, 3]

for n in range(1, int(sqrt(nb) / 6 + 1)):
    premiers.append( n * 6 - 1)
    premiers.append( n * 6 + 1)
print('Nombres premiers à tester', premiers)

test = nb
for facteur in premiers:
    while test % facteur == 0:
        liste.append(facteur)
        test = test / facteur
if test > 1:
    liste.append(int(test))

print('Les facteurs de', nb, 'sont', liste)

[toc] | [prev] | [next] | [standalone]

#4041

Le 25/03/2023 11:54, Dominique a écrit :
>      while test==False:
> 
>          if nb%cpt==0:
>              liste.append(cpt)
>              if nb==cpt:
>                  nb=1
>              else:
>                  nb=nb/cpt
>          else:
>              test=True

Il me semble que toute cette partie peut être réduite à seulement trois lignes :

     while nb%cpt==0:
         liste.append(cpt)
         nb=nb/cpt



-- 
Olivier Miakinen

[toc] | [prev] | [next] | [standalone]

#4042

Le 25/03/2023 12:20, Stefan Ram a écrit :
> Dominique <zzz@aol.com> writes:
>>Ce script aurait-il pu être amélioré ? 
> 
>   Je pense que la signification de « amélioré » dépend de
>   plusieurs facteurs liés au contexte du script, mais ce
>   qui pourrait être fait est :
> 
>   [réponse dans un contexte d'industrialisation]

[OUI à tout]

Pour ma part, j'avais répondu dans le contexte d'efficacité de l'algorithme,
et bien sûr les deux sont des réponses valables.

-- 
Olivier Miakinen

[toc] | [prev] | [next] | [standalone]

#4043

Le 25 mars 2023 Dominique a écrit :

> Ce script aurait-il pu être amélioré ? Je suppose que oui, mais comment ?

Le test nb==cpt est inutile car utilisé qu'une seule fois à la fin. Et la
variable test peut être intégrée dans le while :

nb = int(input('Nombre '))
facteur = 1
test = nb
liste = [1]

while test > 1:
    facteur += 1
    while test % facteur == 0:
        liste.append(facteur)
        test = test / facteur

print('Les facteurs de', nb, 'sont', liste)

[toc] | [prev] | [next] | [standalone]

#4044

Le 25/03/2023 12:28, michel@domain.invalid répondait à Dominique :
> 
> liste = [1]

Ah, tu n'as fait que recopier une erreur qui était déjà dans le programme
d'origine, mais je ne l'avais pas vue alors. Il faut partir d'une liste
vide et pas d'une liste comptant le nombre 1. En effet 1 ne fait pas partie
des nombres premiers, sinon cela rendrait faux le théorème fondamental de
l'arithmétique :
<https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_fondamental_de_l'arithm%C3%A9tique>.

-- 
Olivier Miakinen

[toc] | [prev] | [next] | [standalone]

#4046

Le 25 mars 2023 Olivier Miakinen a écrit :

>> liste = [1]
>
> Ah, tu n'as fait que recopier une erreur qui était déjà dans le programme
> d'origine, mais je ne l'avais pas vue alors. Il faut partir d'une liste
> vide et pas d'une liste comptant le nombre 1. En effet 1 ne fait pas partie
> des nombres premiers, sinon cela rendrait faux le théorème fondamental de
> l'arithmétique :
> <https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_fondamental_de_l'arithm%C3%A9tique>.

Exact, j'optimisais l'algo pas les mathématiques sous-jacentes :)

[toc] | [prev] | [next] | [standalone]

#4048

Le 25/03/2023 à 13:59, michel@domain.invalid a écrit :

> Exact, j'optimisais l'algo pas les mathématiques sous-jacentes :)

Je vous remercie tous pour vos analyses judicieuses. Ce qui est 
intéressant dans le codage, c'est qu'il existe plusieurs chemins pour 
arriver à un même résultat.

Et puis, en parlant de chemins, il m'en reste encore beaucoup à 
parcourir pour améliorer ma pratique de Python :)

Bon dimanche bien pluvieux sur l'orléanais,

-- 
Dominique
Courriel : dominique point sextant ate orange en France
Esto quod es

[toc] | [prev] | [next] | [standalone]

#4049

Le 25/03/2023 à 12:36, Olivier Miakinen a écrit :
> Le 25/03/2023 12:28, michel@domain.invalid répondait à Dominique :
>>
>> liste = [1]
> 
> Ah, tu n'as fait que recopier une erreur qui était déjà dans le programme
> d'origine, mais je ne l'avais pas vue alors. Il faut partir d'une liste
> vide et pas d'une liste comptant le nombre 1. En effet 1 ne fait pas partie
> des nombres premiers, sinon cela rendrait faux le théorème fondamental de
> l'arithmétique :
> <https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_fondamental_de_l'arithm%C3%A9tique>.
> 

Certes, s'il s'agit de décomposer un nombre uniquement en facteurs 
premiers, le 1 est une erreur. Mon script tourne très bien avec une 
initialisation liste=[]

Mon initialisation avec 1 avait une explication : trouver tous les 
diviseurs d'un nombre et les compter, ce à quoi j'avais bien besoin du 1 
(problème 20606 de la revue Tangente, exercice que je n'ai d'ailleurs 
pas réussi à résoudre...)

Facteurs de  360  sont  [1, 2, 2, 2, 3, 3, 5] me donne 7 chiffres, dont 
le 1.

-- 
Dominique
Courriel : dominique point sextant ate orange en France
Esto quod es

[toc] | [prev] | [next] | [standalone]

#4050

Le 26/03/2023 04:24, Dominique a écrit :
> 
> Mon initialisation avec 1 avait une explication : trouver tous les 
> diviseurs d'un nombre et les compter, ce à quoi j'avais bien besoin du 1 
> (problème 20606 de la revue Tangente, exercice que je n'ai d'ailleurs 
> pas réussi à résoudre...)

Voir la fonction diviseurs() dans mon script donné hier à 13 h 44.

> Facteurs de  360  sont  [1, 2, 2, 2, 3, 3, 5] me donne 7 chiffres, dont 
> le 1.

om@kentia:~/tmp$ python3 decompose.py
Nombre : 360
Facteurs premiers de 360 : [2, 2, 2, 3, 3, 5]
Diviseurs de 360 : [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40,
45, 60, 72, 90, 120, 180, 360]
Nombre : 0

Il y a 24 diviseurs.

Note que mathématiquement il n'y a pas besoin d'énumérer les diviseurs pour
savoir combien il y en a. Sachant que 360 = 2³×3²×5¹, il faut ajouter 1 à
chacun des exposants (3, 2, 1 -> 4, 3, 2) et les multiplier :
 (3+1)×(2+1)×(1+1) = 4×3×2 = 24 diviseurs.


-- 
Olivier Miakinen

[toc] | [prev] | [next] | [standalone]

#4052

Le 26/03/2023 13:54, Stefan Ram a écrit :
> Dominique <zzz@aol.com> writes:
>>Facteurs de  360  sont  [1, 2, 2, 2, 3, 3, 5] me donne 7 chiffres, dont 
>>le 1.
> 
>   Je voulais d'abord écrire quelque chose sur le « 1 » hier.
>   Mais j'ai vu sur le web qu'il y avait des pages web où le
>   « 1 » était également mentionné comme un facteur de « 512 ». 
> 
>   En regardant à nouveau les exemples, il semble qu'une
>   distinction soit faite : Le « 1 » est un « facteur », mais ce
>   n'est pas un « facteur premier ». C'est logique, puisque le
>   plus petit nombre premier est deux.

C'est exactement ça.

La décomposition de 360 en facteurs *premiers* est :
 360 = 2 × 2 × 2 × 3 × 3 × 5

Mais les facteurs (diviseurs) de 360 sont :
 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40,
 45, 60, 72, 90, 120, 180, 360.

-- 
Olivier Miakinen

[toc] | [prev] | [next] | [standalone]

#4053

Le 26/03/2023 à 14:06, Olivier Miakinen a écrit :

> Mais les facteurs (diviseurs) de 360 sont :
>   1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40,
>   45, 60, 72, 90, 120, 180, 360.

L'idée du problème était de compter tous les facteurs, mais sans qu'ils 
soient eux-mêmes factorisables (2 et 4, 3 et 6 ou 9...)

Bon, de toutes les manières, je n'ai pas résolu l'exercice :)

-- 
Dominique
Courriel : dominique point sextant ate orange en France
Esto quod es

[toc] | [prev] | [standalone]

Back to top | Article view | fr.comp.lang.python

csiph-web