#

Le facteur Last saved: Oct 29 10:47 AM

- File
- Edit
- View
- Insert
- Cell
- Kernel
- Help

In [1]:

    %pylab inline

    Welcome to pylab, a matplotlib-based Python environment [backend: module://IPython.zmq.pylab.backend_inline].
    For more information, type 'help(pylab)'.

. . .

    x

# Les produits, version brute non ordonnée

In [2]:

    def TriFacteur(n):

        L=[]

        for a in range(n+1):

            for b in range(n+1):

                for c in range(n+1):

                    if a*b*c==n:

                        L.append((a,b,c))

        return L

. . .
In [3]:

    TriFacteur(36)

Out[3]:

    [(1, 1, 36),
     (1, 2, 18),
     (1, 3, 12),
     (1, 4, 9),
     (1, 6, 6),
     (1, 9, 4),
     (1, 12, 3),
     (1, 18, 2),
     (1, 36, 1),
     (2, 1, 18),
     (2, 2, 9),
     (2, 3, 6),
     (2, 6, 3),
     (2, 9, 2),
     (2, 18, 1),
     (3, 1, 12),
     (3, 2, 6),
     (3, 3, 4),
     (3, 4, 3),
     (3, 6, 2),
     (3, 12, 1),
     (4, 1, 9),
     (4, 3, 3),
     (4, 9, 1),
     (6, 1, 6),
     (6, 2, 3),
     (6, 3, 2),
     (6, 6, 1),
     (9, 1, 4),
     (9, 2, 2),
     (9, 4, 1),
     (12, 1, 3),
     (12, 3, 1),
     (18, 1, 2),
     (18, 2, 1),
     (36, 1, 1)]

. . .

    x

# Les produits, version brute ordonnée

In [4]:

    def TriFacteur2(n):

        L=[]

        for a in range(n+1):

            for b in range(a,n+1):

                for c in range(b,n+1):

                    if a*b*c==n:

                        L.append((a,b,c))

        return L

. . .
In [5]:

    TriFacteur2(36)

Out[5]:

    [(1, 1, 36),
     (1, 2, 18),
     (1, 3, 12),
     (1, 4, 9),
     (1, 6, 6),
     (2, 2, 9),
     (2, 3, 6),
     (3, 3, 4)]

. . .

    x

### La clef de la résolution : (1,6,6) et (2,2,9) ont même somme.

In [7]:

    [[x,sum(x)] for x in TriFacteur2(36)]

Out[7]:

    [[(1, 1, 36), 38],
     [(1, 2, 18), 21],
     [(1, 3, 12), 16],
     [(1, 4, 9), 14],
     [(1, 6, 6), 13],
     [(2, 2, 9), 13],
     [(2, 3, 6), 11],
     [(3, 3, 4), 10]]

. . .

    x

# Amélioration du temps

In [8]:

    def TriFacteur3(n):

        L=[]

        A=int(n**(1.0/3.0))

        B=int(n**0.5)

        for a in range(1,A+1):

            for b in range(a,B+1):

                if n%(a*b)==0:

                    c=n//(a*b)

                    if c>=b:

                        L.append((a,b,c))

        return L

. . .
In [9]:

    import time

    def temps(f,L):

        tps=[]# contiendra une liste de temps de calcul

        for j in L:

            start = time.time()

            f(j)

            dureeCalcul=time.time() - start # dureeCalcul=temps de calcul de f(j)

            tps.append(dureeCalcul)

        return tps

. . .
In [24]:

    X=range(50,500,50)

    Y2=temps(TriFacteur2,X)

    Y3=temps(TriFacteur3,X)

    axis([min(X),max(X), -0.2,max(Y2)])

    plot(X,Y2,'r--') #   rouge tireté

    plot(X,Y3,'b*')#   bleu étoilé

    show()

. . .
In [28]:

    X=range(10,20**5,10**4)

    Y3=temps(TriFacteur3,X)

    axis([min(X),max(X), -0.2,max(Y2)])

    plot(X,Y3,'b*')#   bleu étoilé

    show()

. . .
In [ ]:

. . .
Close Expand Open in Pager Close