Deprecated: Array and string offset access syntax with curly braces is deprecated in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/init.php on line 563
decomposition_en_facteurs_premiers [Les recettes Python de Tyrtamos]

Outils pour utilisateurs

Outils du site


decomposition_en_facteurs_premiers

Ceci est une ancienne révision du document !



Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/parser/handler.php on line 1458

Warning: preg_match(): Compilation failed: invalid range in character class at offset 3565 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/parser/lexer.php on line 118
A PCRE internal error occured. This might be caused by a faulty plugin

====== Décomposition d'un nombre en facteurs premiers ====== Pour la définition de ce qu'est un nombre premier, voir ici: [[http://fr.wikipedia.org/wiki/Nombre_premier]] On peut toujours décomposer un nombre entier quelconque en facteurs premiers. Par exemple: facteurs(50) => 2*5*5 Bien entendu, un nombre premier ne trouve que lui-même comme facteur premier! Le principe du calcul est assez trivial, et consiste à faire des divisions entières systématiques avec divmod(). Cette fonction renvoie une liste de 2 valeurs: le résultat de la division entière et son reste. Si le reste est nul, c'est que la division est exacte, et on a trouvé un facteur de plus. On l'ajoute à la liste F, on remplace le n précédent par le résultat de cette division, et on recommence. La liste F contient à la fin tous les facteurs. On utilise en plus une astuce pour gagner du temps: on commence par trouver tous les facteurs "2" (s'il y en a), ce qui permet après de n'essayer que les nombres impairs. Pour des valeurs de n importantes, on divise ainsi les essais par 2. Les tentatives de division s'arrêtent à racine de n, parce que si on n'a pas trouvé de facteur avant, on n'en trouvera plus, et donc le n en question est premier (et on a donc fini la décomposition). Pour calculer la racine carrée de n, on utilise la fonction lsqrt() définie ici: [[http://python.jpvweb.com/mesrecettespython/racine_entiere]]. On aurait pu faire un test avec i*i>n, mais cela conduirait à faire la multiplication i*i pour chaque valeur de i, alors que la racine de n ne change que lorsque n change. Voici le code: <code python> #!/usr/bin/python # -*- coding: utf-8 -*- def facteurs(n): """facteurs(n): décomposition d'un nombre entier n en facteurs premiers""" F = [] if n==1: return F # recherche de tous les facteurs 2 s'il y en a while n>=2: x,r = divmod(n,2) if r!=0: break F.append(2) n = x # recherche des facteurs 1er >2 i=3 rn = lsqrt(n)+1 while i<=n: if i>rn: F.append(n) break x,r = divmod(n,i) if r==0: F.append(i) n=x rn = lsqrt(n)+1 else: i += 2 return F # exemple d'utilisation: print facteurs(100) # affiche [2,2,5,5] print facteurs(123456789) # affiche [3,3,3607,3803] print facteurs(12345678901234567890) # affiche [2,3,3,5,101,3541,3607,3803,27961L] # et test avec un nombre premier print facteurs(4291979) # affiche [4291979] </code> \\ Bien que passant par un calcul systématique "bête", cette fonction est rapide. Par exemple: <code python> print facteurs(12345678901234567890) [2, 3, 3, 5, 101, 3541, 3607, 3803, 27961] </code> Résultat trouvé en moins d'un 1/10 de seconde (essayez donc de faire ça à la main...). La rapidité du calcul dépend de la quantité des facteurs et de leur taille. Le temps le plus long étant obtenu, pour une taille donnée, avec un nombre premier, ou avec un nombre composé de 2 nombres premiers grands. Par exemple: <code python> print facteurs(6082717798076598743) [1536921011, 3957729613L] </code> Ce qui prend environ 15 mn de calcul. Par contre, pour traiter des nombres de plusieurs centaines de chiffres comme on en trouve en cryptographie, il faudra nécessairement développer d'autres méthodes... \\ On obtient donc le résultat sous forme de liste, mais vous souhaitez peut-être la transformer en expression avec tous les facteurs prêts à être re-multipliés. Alors, vous pouvez créer la fonction suivante: <code python> def mulfacteurs(L): """ mulfacteurs(L): présente la liste des facteurs en facteurs multipliés""" if L==[]: ch = "" else: ch = "%s" % L[0] for k in xrange(1,len(L)): ch = ch + "*" + "%s" % L[k] return ch </code> Dans ce cas, la liste précédente est transformée en: "2*3*3*5*101*3541*3607*3803*27961" Comme c'est une expression sous forme de chaine vous pouvez en demander le calcul par eval(): eval("2*3*3*5*101*3541*3607*3803*27961") qui redonne bien (heureusement! :-D ) le nombre initial donné: 12345678901234567890. \\ Vous pouvez tester la fonction facteurs(n) avec la Calculext ici: [[http://calculext.jpvweb.com]], mais soyez raisonnable: avec un nombre trop grand, vous risquez de dépasser le temps maxi de calcul autorisé sur le serveur. \\ Amusez-vous bien! <html> <head> <style type="text/css"> <!-- body {background-image:url(fondcorps.jpg);} --> </style> </head> <body> </body> </html>

decomposition_en_facteurs_premiers.1231501523.txt.gz · Dernière modification: 2009/01/09 12:45 (modification externe)

Outils de la page