Outils pour utilisateurs

Outils du site


decomposition_en_facteurs_premiers

Ceci est une ancienne révision du document !


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. 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! :-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.

decomposition_en_facteurs_premiers.1215012358.txt.gz · Dernière modification: 2008/07/02 17:25 de tyrtamos

Outils de la page