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

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)