Path: ...!eternal-september.org!feeder.eternal-september.org!news.gegeweb.eu!gegeweb.org!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 12:11:32 +0100
Organization: There's no cabale
Lines: 33
Message-ID: <tvmkt4$bkd$1@cabale.usenet-fr.net>
References: <tvmju0$259vr$1@dont-email.me>
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 1679742692 11917 93.28.89.200 (25 Mar 2023 11:11:32 GMT)
X-Complaints-To: abuse@usenet-fr.net
NNTP-Posting-Date: Sat, 25 Mar 2023 11:11:32 +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: <tvmju0$259vr$1@dont-email.me>
Bytes: 2170

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