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

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 12:11 +0100
Organization	There's no cabale
Message-ID	<tvmkt4$bkd$1@cabale.usenet-fr.net> (permalink)
References	<tvmju0$259vr$1@dont-email.me>

Show all headers | View raw

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

Back to fr.comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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