Problème Euler 245 (optimisation du code)

Version imprimable

Bonjour à tous,
Je suis nouvelle sur ce forum et j'aimerais solliciter votre aide, sur comment optimiser mon code, qui est la solution au problème Euler 245, sur le site hackerrank, mon code fonctionne quand il est testé sur un petit chiffre 5,6,7. Par contre quand je soumets mon code et que des tests sont effectués sur des nombres très élevé, j'ai l'erreur que le code met trop de temps à s’exécuter.
Voici mon code et je vous remercie d'avance pour votre aide
Code:

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 30 31 32 def diviseurs_communs(a,b): diviseurs_a=[i for i in range(1,a+1) if a%i==0] diviseurs_b=[i for i in range(1,b+1) if b%i==0] div_a=set(diviseurs_a) div_b=set(diviseurs_b) div_commun=list(div_a.intersection(div_b)) return(div_commun) def Euler_toti(n): if n==1: eul=1 return(eul) else : eul=[1 for i in range(1,n) if len(diviseurs_communs(n,i))==1] eule=sum(eul) return(eule) def Corresilience(N): cor=[i for i in range(2,N+1) if Euler_toti(i)==(i-1)/(i-Euler_toti(i))] corre=sum(cor) print(corre) return(corre) N=input() Corresilience(int(N))

Salut,

Citation:

Envoyé par super_jeje

Par contre quand je soumets mon code et que des tests sont effectués sur des nombres très élevé, j'ai l'erreur que le code met trop de temps à s’exécuter.

Le durée dépend du nombre d'instructions à exécuter qui reflète la complexité de l'algorithme que vous avez choisi de coder.

Et si votre algorithme à une complexité exponentielle, "optimiser" le code sera juste une perte de temps: mieux vaudra chercher un meilleur algorithme!

A part çà si la durée dépend du nombre d'instructions, toutes les instructions exécutées alors que ce n'est pas nécessaire devront/pourront être évité.
Relisez votre code:
Code:

1 2 3 4 5 6 7 8 def diviseurs_communs(a,b): diviseurs_a=[i for i in range(1,a+1) if a%i==0] diviseurs_b=[i for i in range(1,b+1) if b%i==0] ... def Euler_toti(n): ... else : eul=[1 for i in range(1,n) if len(diviseurs_communs(n,i))==1]
va calculer n fois diviseurs_a=[i for i in range(1,a+1) if a%i==0] alors qu'une seule suffirait.

Après côté algo. il s'agit de trouver les entiers dans 1..n divisibles par un des diviseurs premiers d'un n non premier (s'il est premier, pas la peine de faire tout çà)... mais le forum algo est ici.

- W

Je vous remercie pour votre réponse, je vais aller poster sur le forum algo, en fait j'ai réecris le code, mais toujours le même souci

Code:

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
 
import math
 
def Euler_toti(n):
     if n==1:
         eul=1
         return(eul)
     else :
        eul=[math.gcd(n,i)==1 for i in range(1,n) ]
 
     eule=sum(eul) 
 
     return(eule)
 
 
 
def Corresilience(N):
 
   cor=[i for i in range(2,N+1) if Euler_toti(i)==(i-1)/(i-Euler_toti(i))]
   corre=sum(cor)
   print(corre)
   return(corre)
 
N=input()
Corresilience(int(N))

28/12/2019, 18h48
flapili

pour les anglophobes tel que moi est t'il possible d'avoir un énoncé ?

de ce que je comprends il faut trouver la somme des numérateurs des fractions irréductibles entre 1/n et n-1/n c'est ça ?
28/12/2019, 19h44
danielhagnoul

Citation:

Envoyé par flapili

pour les anglophobes tel que moi est t'il possible d'avoir un énoncé ?

de ce que je comprends il faut trouver la somme des numérateurs des fractions irréductibles entre 1/n et n-1/n c'est ça ?

Après 50 je ne trouve pas en FR : https://www.lucaswillems.com/fr/arti...oblemes-1-a-50

C'est trop spécialisé pour que je comprenne bien en anglais.
28/12/2019, 20h26
wiztricks

Citation:

Envoyé par super_jeje

Je vous remercie pour votre réponse, je vais aller poster sur le forum algo, en fait j'ai réecris le code, mais toujours le même souci

En remplaçant diviseurs_communs par math.gcd vous êtes passé d'une complexité d'un ordre de N*N*2*N à un ordre de N*N*f(N) où f(N) est la complexité de math.gcd en fonction de N.
note: c'est pas parce que vous réduisez le nombre de lignes de code en déléguant le boulot que çà va ira plus vite!

- W
28/12/2019, 22h51
super_jeje

Ayant l'habitude de coder avec des machines ayant beaucoup de RAM, je ne m'étais jamais posé la question d'optimisation du code, car je n'ai jamais eu de problème.
Pour ce qui est du problème d'Euler 245, ce qui est demandé c'est que pour un entier N avec i >1 et i<=N il faut
il faut avoir la somme des i, telle que l'indicatrice de Euler de i que j'ai appelée Euler_toti, soit égale à l'inverse de la fonction appelé de corresilience qui est égale à C(i)=(i-Euler_toti(i)) /(i-1).
Par exemple pour 5, c'est égale à 10 car on
on a Euler_toti(2)=1 et C(2)=1
Euler_toti(3)=2 et C(3)=1/2
Euler_toti(4)=2 et C(4)=2/3
Euler_toti(5)=4 et C(2)=1/4

Ainsi 2 +3 + 5 =10
28/12/2019, 22h53
super_jeje

Citation:

Envoyé par danielhagnoul

Après 50 je ne trouve pas en FR : https://www.lucaswillems.com/fr/arti...oblemes-1-a-50

C'est trop spécialisé pour que je comprenne bien en anglais.

J'ai posté une explication
28/12/2019, 22h54
super_jeje

Citation:

Envoyé par wiztricks

En remplaçant diviseurs_communs par math.gcd vous êtes passé d'une complexité d'un ordre de N*N*2*N à un ordre de N*N*f(N) où f(N) est la complexité de math.gcd en fonction de N.
note: c'est pas parce que vous réduisez le nombre de lignes de code en déléguant le boulot que çà va ira plus vite!

- W

J'ai suivi des conseils que j'ai trouvé sur internet par rapport à la complexité, le code est certes plus lisible, mais la complexité demeure, je ne m'y connais pas en complexité cela est mon point faible
28/12/2019, 23h41
flapili

Citation:

Envoyé par super_jeje

Ayant l'habitude de coder avec des machines ayant beaucoup de RAM, je ne m'étais jamais posé la question d'optimisation du code, car je n'ai jamais eu de problème.
Pour ce qui est du problème d'Euler 245, ce qui est demandé c'est que pour un entier N avec i >1 et i<=N il faut
il faut avoir la somme des i, telle que l'indicatrice de Euler de i que j'ai appelée Euler_toti, soit égale à l'inverse de la fonction appelé de corresilience qui est égale à C(i)=(i-Euler_toti(i)) /(i-1).
Par exemple pour 5, c'est égale à 10 car on
on a Euler_toti(2)=1 et C(2)=1
Euler_toti(3)=2 et C(3)=1/2
Euler_toti(4)=2 et C(4)=2/3
Euler_toti(5)=4 et C(2)=1/4

Ainsi 2 +3 + 5 =10

ça reste incompréhensible:piou:
29/12/2019, 00h24
super_jeje

Citation:

Envoyé par flapili

ça reste incompréhensible:piou:

Si on veut calculer pour N alors

On calcule la somme tous les i avec 1<i<=N, telle que Euler_toti(i)=1/C(i)
avec C(i)=(i-Euler_toti(i))/(i-1)

Je ne trouve pas plus rapide que ce code :

Code:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#! python 3
# coding: utf-8
 
from termcolor import cprint
from math import gcd
 
 
def phi_euler(n):
    """Tuple contenant la valeur de phi et les diviseurs premiers avec n"""
    lst = []
    for k in range(1, n+1):
        if gcd(n, k) == 1:
            lst.append(k)
    return (len(lst), lst)
 
 
# print(phi_euler(7000))
 
def corresilience(N):
    lst = []
    for k in range(2, N+1):
        phi = phi_euler(k)[0]
        if phi == (k - 1)/(k - phi):
            lst.append(k)
    return sum(lst)
 
 
for k in range(5, 5006, 500):
    cprint("corresilience de {} = {}".format(k, corresilience(k)), 'green')
 
"""
corresilience de 5 = 10
corresilience de 505 = 22039
corresilience de 1005 = 76127
corresilience de 1505 = 165040
corresilience de 2005 = 279053
corresilience de 2505 = 423315
corresilience de 3005 = 596824
corresilience de 3505 = 785762
corresilience de 4005 = 1021511
corresilience de 4505 = 1267655
corresilience de 5005 = 1553139
"""

Avec mémoïsation:

Code:

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
30
31
32
33
34
#! python 3
# coding: utf-8
 
from termcolor import cprint
from math import gcd
 
"""Mémoïzation"""
phi_memo = {}
 
 
def phi_euler(n):
    """Tuple contenant la valeur de phi et les diviseurs premiers avec n"""
    if not n in phi_memo:
        lst = []
        for k in range(1, n+1):
            if gcd(n, k) == 1:
                lst.append(k)
        phi_memo[n] = (len(lst), lst)
    return phi_memo[n]
 
 
# print(phi_euler(7000))
 
def corresilience(N):
    lst = []
    for k in range(2, N+1):
        phi = phi_euler(k)[0]
        if phi == (k - 1)/(k - phi):
            lst.append(k)
    return sum(lst)
 
 
for k in range(5, 5006, 500):
    cprint("corresilience de {} = {}".format(k, corresilience(k)), 'green')

Citation:

Envoyé par danielhagnoul

Avec mémoïsation:

Code:

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
30
31
32
33
34
#! python 3
# coding: utf-8
 
from termcolor import cprint
from math import gcd
 
"""Mémoïzation"""
phi_memo = {}
 
 
def phi_euler(n):
    """Tuple contenant la valeur de phi et les diviseurs premiers avec n"""
    if not n in phi_memo:
        lst = []
        for k in range(1, n+1):
            if gcd(n, k) == 1:
                lst.append(k)
        phi_memo[n] = (len(lst), lst)
    return phi_memo[n]
 
 
# print(phi_euler(7000))
 
def corresilience(N):
    lst = []
    for k in range(2, N+1):
        phi = phi_euler(k)[0]
        if phi == (k - 1)/(k - phi):
            lst.append(k)
    return sum(lst)
 
 
for k in range(5, 5006, 500):
    cprint("corresilience de {} = {}".format(k, corresilience(k)), 'green')

Bonjour merci pour votre aide mais toujours le même problème Runtime error, c'est assez frustrant d'avoir ce type d'erreur, je pense que je vais abandonner pour ce problème

Avec une solution externe pour le calcul de phi_euler, c'est plus rapide mais toujours trop lent à mon avis.

Code:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#! python 3
# coding: utf-8
 
from termcolor import cprint
from math import sqrt
 
"""Mémoisation"""
phi_memo = {}
 
 
def phi_euler(n):
    """
    Calcul de l'indicatrice d'Euler par différences
    Méthode de yoshi le 24-10-2013 18:18:22
    Sur http://www.bibmath.net/forums/viewtopic.php?id=6336
    Dans le message n° 10
    """
    def diviseurs(n):
        D, racine = [1], int(sqrt(n))
        fin = racine+1
        for d in range(2, fin):
            if n % d == 0:
                D.extend([d, n//d])
        D = sorted(set(D))
        return D
 
    if not n in phi_memo:
        D = diviseurs(n)
        phi = [1]
 
        for div in D:
            if div > 1:
                D_i, q = [d for d in D if div % d == 0 and d < div], 0
                for d in D_i:
                    q += phi[D.index(d)]
                p = div - q
                phi.append(p)
        phi_memo[n] = n - sum(phi)
 
    return phi_memo[n]
 
 
def corresilience(N):
    lst = []
    for k in range(2, N+1):
        phi = phi_euler(k)
        if phi == (k - 1)/(k - phi):
            lst.append(k)
    return sum(lst)
 
 
for k in range(5, 500000, 500):
    cprint("corresilience de {} = {}".format(k, corresilience(k)), 'green')

29/12/2019, 23h29
wiztricks

Salut,

Citation:

Envoyé par super_jeje

ce qui est demandé c'est que pour un entier N avec i >1 et i<=N il faut
il faut avoir la somme des i, telle que l'indicatrice de Euler de i que j'ai appelée Euler_toti, soit égale à l'inverse de la fonction appelé de corresilience qui est égale à C(i)=(i-Euler_toti(i)) /(i-1).

Si c'est ce que vous cherchez, vous savez que pour tout p premier C(p) = 1 / (p - 1) i.e. l'inverse de Euler_toti(p) (= p - 1)... Dans ce cas, votre problème se ramène à effectuer la somme des nombres premiers inférieurs à N.

- W

Citation:

Envoyé par wiztricks

[...] Dans ce cas, votre problème se ramène à effectuer la somme des nombres premiers inférieurs à N. - W

Exact !

N = 5, liste = [2, 3, 5]
corresilience de 5 = 10
N = 10, liste = [2, 3, 5, 7]
corresilience de 10 = 17
N = 15, liste = [2, 3, 5, 7, 11, 13]
corresilience de 15 = 41
N = 20, liste = [2, 3, 5, 7, 11, 13, 17, 19]
corresilience de 20 = 77
N = 25, liste = [2, 3, 5, 7, 11, 13, 17, 19, 23]
corresilience de 25 = 100
N = 30, liste = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
corresilience de 30 = 129
N = 35, liste = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
corresilience de 35 = 160
N = 40, liste = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
corresilience de 40 = 197
N = 45, liste = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
corresilience de 45 = 281

Je n'avais pas eu la curiosité d'imprimer cette liste ! :aie:

Fuseau horaire GMT +2. Il est actuellement 11h13.

Partenaire : Hébergement Web