Path: ...!3.us.feeder.erje.net!3.eu.feeder.erje.net!feeder.erje.net!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!cleanfeed3-b.proxad.net!nnrp1-1.free.fr!not-for-mail
From: michel@domain.invalid
Newsgroups: fr.comp.lang.python
Subject: Re: =?utf-8?Q?D=C3=A9composition?= d'un nombre en facteurs
 premiers.
References: <tvmju0$259vr$1@dont-email.me> <tvmkt4$bkd$1@cabale.usenet-fr.net>
	<tvmqb9$crr$1@cabale.usenet-fr.net>
User-Agent: Gnus
Mail-Copies-To: never
Date: Sat, 25 Mar 2023 14:10:28 +0100
Cancel-Lock: sha1:Bb8hKBo3+iXYb5GJNUHlFgjAP1g=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Lines: 58
Message-ID: <641ef3d6$1$3199$426a74cc@news.free.fr>
Organization: Guest of ProXad - France
NNTP-Posting-Date: 25 Mar 2023 14:15:02 CET
NNTP-Posting-Host: 82.66.159.6
X-Trace: 1679750102 news-3.free.fr 3199 82.66.159.6:36040
X-Complaints-To: abuse@proxad.net
Bytes: 2960

Le 25 mars 2023 Olivier Miakinen a =C3=A9crit :

> Le 25/03/2023 12:11, je r=C3=A9pondais =C3=A0 Dominique :
>>=20
>> Tu peux m=C3=AAme partir d'un cpt de la forme 6n+1, faire des cpt+=3D6, =
et tester
>> la division par cpt et par (cpt+4). Comme =C3=A7a tu ne testes plus aucu=
n multiple
>> de 2 ou de 3.
>
> J'ai fait exactement =C3=A7a. Apr=C3=A8s avoir test=C3=A9 la division par=
 2 et par 3 je
> ne teste plus que les divisions par 6k-1 et 6k+1. Apr=C3=A8s l'affichage =
des
> facteurs premiers j'ai aussi ajout=C3=A9 l'affichage de tous les diviseur=
s,
> mais je ne suis pas s=C3=BBr que mon code soit optimal. Merci de me dire =
si
> je peux faire mieux.

Pour pr=C3=A9senter =C3=A7a un peu autrement, =C3=A7a revient =C3=A0 cherch=
er les
nombres premiers qui peuvent =C3=AAtre diviseurs et =C3=A0 ne tester qu'eux.
Je ne cherche pas =C3=A0 exclure tous les nombres qui ne sont pas premiers =
car
=C3=A7a serait redondant avec le test de division du nombre test=C3=A9.


'''
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=C3=A9ment divisible par un nombre premier.
Un diviseur d'un nombre est soit lui-m=C3=AAme (il est premier) soit un
nombre inf=C3=A9rieur =C3=A0 sa racine carr=C3=A9e.
Les nombres premiers (hormis 2 et 5) se terminent tous par 1, 3, 7 ou 9.=20
Les nombres 0 et 1 ne sont pas premiers.
'''

from math import sqrt

nb =3D int(input('Nombre '))
liste =3D []
premiers =3D [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 =C3=A0 tester', premiers)

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

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