Path: ...!eternal-september.org!feeder.eternal-september.org!news.gegeweb.eu!gegeweb.org!usenet-fr.net!.POSTED!not-for-mail From: Olivier Miakinen 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: References: 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: 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