Discussion :

[bouchelliga]

Pour décomposer un entier en python y'a t il mieux que ça

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def div(a): 
#donne les diviseur d'un entier#
    l=[]
    for i in range(1,a+1):
        if a%i==0:l.append(i)
    return(l)
def nomb_prem_inf(n):
#donne les entiers premiers inf a n #
    k=[]
    for i in range(1,n):
        if div(i)==[1,i]:k.append(i)
    return k
def div_prem(n):
#donne les diviseurs premiers inf a n#
    j=[]
    for i in nomb_prem_inf(n):
        if n%i==0:j.append(i)
    return j
def decomp(n):
#donne la decomposition en facteurs premiers de n#
    e=[]
    for i in div_prem(n):
        for j in range(1,n):
            if n%(i**j)==0:e.append(i)
    return e
n=eval(input("saisir n:"))
print("diviseur de n:",div(n))
print("nombre premier inf < n:",nomb_prem_inf(n))
print("decomposition en fact premier de n:",decomp(n))

[lg_53]

Déjà ton programme ne fonctionne pas bien si le nombre saisi par l'utilisateur est déjà premier. Je t'invite à regarder ça.


Le calcul des nombres premiers est très couteux, surtout quand on commence à mettre des grands nombre. Il faut donc :
1) Essayer de faire un algorithme de détection de nombre premiers qui soit un peu plus malin que de tester tous les nombre un par un.
2) Ne calculer que les nombres premiers nécessaires et pas plus. Si je prends par exemple le nombre 350 = 2*5*5*7, j'ai pas besoin de savoir que 349 est un nombre premier...


1) Ensuite, pour calculer un nombre premier :
- 1 n'est pas premier
- 2 est le seul entier premier pair
Sachant ca, au lieu de tester si tous les nombres sont premiers, tu peux tester que les impairs.
De plus on n'a pas besoin d'avoir toute la liste des diviseurs ! Suffit d'en trouver un seul qui ne soit ni 1 ni le nombre lui même pour conclure que le nombre n'est pas premier.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def est_premier(n) :
    res = True  ### Si on ne trouve pas de diviseurs autre que 1 et n le résultat est vrai
 
    if (n % 2 == 0) :            ### Cas n pair
        if n != 2 : res=False   ### Si n est pair mais n'est pas 2, alors n n'est pas premier ici
    else :                             ### Cas impair
        d=3                           ### On démarre à 3
        while d*d <= n :       ### Rien ne sert de tester jusqu'à n. Les diviseurs fonctionnent par pair, l'un étant <= à sqrt(n) l'autre >= à sqrt(n)
            if n % d == 0 :      ### On a trouvé un diviseur !
                res=False          ### On met donc le résultat à False
                break                ###  et on force la sortie de la boucle while, car il est complètement inutile d'aller plus loin
            d += 2                  ### On incrémente de 2, car on ne teste ici que les nombres impairs
    return res

2) Pour régler ce point le mieux serait donc d'écrire une fonction prochain_nombre_premier(n), qui te retournes le prochain nombre premier strictement supérieur à n qui s'appuie sur la fonction est_premier bien sûr. Ensuite dans la fonction decomp(n), tu pars de d=2 et tu divises n par 2 autant de fois qu'il faut tant que ca reste entier. Quand le reste de la division n'est plus nul, tu appelles prochain_nombre_premier(d) (qui va te retourner 3 si d=2, 5 si d=3, etc..) et tu reteste à nouveau la division etc..
Et plutot que de tester qqch du style n%(i**j)==0 c'est mieux de dire au début de ton code q=n, lorsque tu trouves un diviseur d, tu fais q=q/d et tu recommences sur q itérativement (et pas sur n). Ainsi q va diminuer, jusqu'à temps d'être lui même un nombre premier qui sera le dernier de ta décomposition.

[tyrtamos]

Bonjour,

Pour décomposer un nombre entier en facteurs premiers par la méthode des divisions, il y a quelques astuces pour gagner du temps.

- Puisque "2" est le seul nombre pair qui soit premier, il faut commencer par éliminer tous les facteurs "2": après, on ne testera que les nombres impairs en tant que diviseurs à partir de 3. On divise ainsi par 2 le nombre de divisions à faire.

- à chaque fois qu'on a trouvé un facteur i, on calcule le nouveau n = n//i, et on continue les divisions avec le nouveau n et le diviseur i (on ne revient pas à 3).

- Pour un "n" donné, il n'est pas utile pour un diviseur de dépasser racine carré de n. Reste à trouver une manière élégante et rapide de calculer la racine carré entière d'un nombre entier (voir la méthode de Heron d'Alexandrie).

- Essayer tous les nombres impairs donne pas mal de divisions inutiles. Par exemple, on a essayé 3, puis 5 qui n'ont pas marché, mais on va encore essayer 15 alors qu'on sait déjà qu'il ne marchera pas. On peut donc accélérer encore en ayant à l'avance une liste de, par exemple, les 1000 premiers nombres premiers, et en commençant les divisions par eux. Au delà, on continue avec les nombres impairs.

Il y a peut être encore d'autres astuces, mais ces quatre-là permettent déjà de bon calculs. Par exemple, on décompose le nombre 12345678901234567890 en [2, 3, 3, 5, 101, 3541, 3607, 3803, 27961] quasi instantanément. Mais le temps s'allonge lorsque les plus petits facteurs trouvés augmentent en taille, le temps maxi étant quand on essaie de décomposer un grand nombre déjà premier.

Quand le nombre devient trop grand pour la méthode des divisions, il existe d'autres méthodes plus complexes comme par exemple la méthode de Pollard Rho qui permet d'obtenir en Python des résultats sur des nombres de 24 chiffres en quelques secondes. Par exemple: 309621299363859380750381 => [19, 491, 7366397, 4505475319937]

Il existe des méthodes encore plus complexes comme la courbe elliptique de Lenstra. D'après ce que j'ai déjà essayé, même avec cette dernière méthode, il parait difficile de factoriser des nombres de plus de 50 chiffres en Python sur nos PC. On est encore très loin des nombres de 600 chiffres rencontrés dans le cryptage RSA, et heureusement! Mais l'arrivé des ordinateurs quantiques va peut-être changer tout ça?

Bon courage!

[bouchelliga]

Merci infiniment

[bouchelliga]

Merci infiniment