Ceci est une ancienne révision du document !
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. Pour éviter l'utilisation de sqrt(), on fait le test sur i*i>n.
Voici le code:
#!/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=divmod(n,2) if x[1]==0: f.append(2) n=x[0] else: break # recherche des facteurs 1er >2 i=3 while (i<=n): if i*i>n: f.append(n) break x=divmod(n,i) if x[1]==0: f.append(i) n=x[0] 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]
Bien que passant par un calcul systématique “bête”, cette fonction est rapide. Par exemple:
facteurs(12345678901234567890) trouve [2, 3, 3, 5, 101, 3541, 3607, 3803, 27961] en moins d'un 1/10 de seconde (essayez donc de faire ça à la main…)
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:
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
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! ) 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.