Bonjour,
J'ai un souci pour une fonction qui calcul l'indicatrice d'Euler en python: je vous met le code

#Fonction retournant le PGCD
def PGCD(a,b):
	r=a%b
        if (r==0):
            return b
        else:
            return PGCD(b,r)
            

# Fonction déterminant si deux nombres sont premiers entre eux
# Retourne "TRUE" si c'est le cas.
def estPremier(a,b):
	return PGCD(a,b)==1


# L'indicatrice d'Euler φ est la fonction de l'ensemble des entiers strictement positifs dans lui-même, qui à n associe le nombre d'entiers strictement positifs inférieurs ou égaux à n et premiers avec n
# Par exemple :
# φ(8) = 4 car parmi les nombres de 1 à 8, seuls les quatre nombres 1, 3, 5 et 7 sont premiers avec 8,
# φ(1) = 1 car 1 est premier avec lui-même (c'est le seul entier naturel qui vérifie cette propriété
def phi(m):
    if m == 1:
        return 1
    else:
        r = [n for n in range(1,m) if estPremier(m,n)]   # r = liste des n allant de 1 à m-1 tel que m et n soient premiers entre-eux. 
        return len(r)

Nous avons un souci quand on le test avec des très grands nombres au niveau du range, il affiche l'erreur suivante:OverflowError: long int too large to convert to int

Je fais appelle à vous pour savoir s'il y a une autre solution pour parcourir la liste avec de très grand nombre.
Merci d'avance

Tu peux déjà améliorer ta fonction pgcd avec le module fractions

ou si tu ne veux pas utiliser de module tout fait, transforme ta fonction récursive en fonction itérative qui en générale est moins gourmande.

def PGCD(a,b):
	while a != b:
	    if a > b:
	        a -= b
	    else:
	        b -= a
	return a

Edit : Je viens de comprendre, que ce qui intéressait était de savoir si le rapport entre deux nombres est premier.

Bonjour,

Sur quelle ligne est l'erreur ?
Je n'arrive pas à reproduire le problème : avec Python 2.6, j'ai "OverflowError: range() result has too many items", et avec Python 3, il n'y a pas d'erreur. Quelle version de Python utilises-tu ?

ProgVal

PS : au niveau de ton style de programmation : il serait bon d'éviter de mélanger les tabulations et les espaces, pour indenter (par exemple, ça m'a posé un problème en copiant dans Vim, qui transforme automatiquement les tabulations en quatre espaces lorsque je programme en Python), ainsi que d'éviter de faire des lignes qui dépassent 80 caractères.

Si tu utilises Py2.x, utilises xrange au lieu de range.

Tout d'abord merci pour vos réponses.
Pour les tabulations je suis désolée mais au début je programmais avec emacs et je suis passée avec gédit (plus simple pour mettre en commentaire) c'est de la que vient le changement !
Pour Catapoulpe !, encore désolée je me suis trompé en recopiant l'erreur c'est bien: OverflowError: range() result has too many items que j'obtiens !
Pour python j'utilise la version Python 2.5.2 !
Et pour quelqu'un d'autre j'ai dejà essayé avec xrange() et ça ne marche toujours pas !

Peut être faudrait-il changer la façon de calculer l'indicatrice d'Euler mais je n'ai pas d'idée ?

EDIT : Avec quelque recherche pour modifer la fonction j'ai trouver un code qui fonctionne ! Merci de votre aide !

On peut savoir ce que tu as modifié?

La fonction pgcd ou la fonction phi?

On peut voir le code aussi ?

Le problème vient des listes qui sont très limitées. Premièrement, si tu utilise Python 2, il fallait effectivement remplacer range() qui retourne une liste par xrange() qui retourne un itérateur. Mais il fallait aussi modifier ta fonction phi et remplacer la ligne contenant une liste comprehension. Par exemple :

x = 0
for n in xrange(1, m):
    if estPremier(m, n):
        x += 1
return x

Pour calculer l'indicatrice d'Euler, il y a de bien meilleures méthodes. Par exemple, si m et n sont premiers entre euh, tu as phi(mn) = phi(m) * phi(n), et si n est premier, phi(n) = n - 1. Du coup, hop, tu décomposes ton entrée en produit de facteurs premiers (c'est comme la vie, c'est pas cher), et tu fais le produit (sans oublier le -1).

Citation : Maxibolt

Pour calculer l'indicatrice d'Euler, il y a de bien meilleures méthodes. Par exemple, si m et n sont premiers entre euh, tu as phi(mn) = phi(m) * phi(n), et si n est premier, phi(n) = n - 1. Du coup, hop, tu décomposes ton entrée en produit de facteurs premiers (c'est comme la vie, c'est pas cher), et tu fais le produit (sans oublier le -1).

En effet, quoique ta description soit assez incomplète (quid des nombres primaires ?) d'ailleurs, au passage, un peu de code Python(*) illustrant tes dires aurait été bienvenu et t'aurait peut-être fait prendre conscience des imprécisions de ta description. Mais tu emploies l'expression "par exemple" ce qui laisse penser que tu connais d'autres "meilleures méthodes" que la décomposition en facteurs premiers. Desquelles s'agit-il ?



(*) EDIT Une petite proposition différente (en apparence seulement mais assez lente tout de même) de la méthode classique de décomposition en facteurs premiers :

# Python 2.6
def phi(n):
    if n==1:
        return 1
    for d in range(2,n+1):
        if n%(d*d)==0:
            return d*phi(n/d)
        elif n%d==0:
            return (d-1)*phi(n/d)

print phi(2011*10000)

8040000

Citation : candide

Citation : Maxibolt

Pour calculer l'indicatrice d'Euler, il y a de bien meilleures méthodes. Par exemple, si m et n sont premiers entre euh, tu as phi(mn) = phi(m) * phi(n), et si n est premier, phi(n) = n - 1. Du coup, hop, tu décomposes ton entrée en produit de facteurs premiers (c'est comme la vie, c'est pas cher), et tu fais le produit (sans oublier le -1).

En effet, quoique ta description soit assez incomplète (quid des nombres primaires ?) d'ailleurs, au passage, un peu de code Python(*) illustrant tes dires aurait été bienvenu et t'aurait peut-être fait prendre conscience des imprécisions de ta description. Mais tu emploies l'expression "par exemple" ce qui laisse penser que tu connais d'autres "meilleures méthodes" que la décomposition en facteurs premiers. Desquelles s'agit-il ?



(*) EDIT Une petite proposition différente (en apparence seulement mais assez lente tout de même) de la méthode classique de décomposition en facteurs premiers :

# Python 2.6
def phi(n):
    if n==1:
        return 1
    for d in range(2,n+1):
        if n%(d*d)==0:
            return d*phi(n/d)
        elif n%d==0:
            return (d-1)*phi(n/d)

print phi(2011*10000)

8040000

Désolé pour cette réponse tardive. Effectivement, j'ai pas cherché à donner une réponse super précise mais plutôt à l'aiguiller vers une possible solution. Et non, je ne connais pas d'autre méthode, mais je pense qu'il en existe sûrement : comprends le « par exemple » comme un « il est au moins possible de ».

Citation : Maxibolt

Et non, je ne connais pas d'autre méthode, mais je pense qu'il en existe sûrement

Hum, ça m'étonnerait quand même. La sécurité de RSA est basée là-dessus. Le RSA modulus <math>\(n\)</math> est public, si on savait calculer <math>\(\varphi(n)\)</math> autrement qu'en connaissant les deux facteurs premiers de <math>\(n\)</math> alors on pourrait inverser l'exposant RSA (c'est l'inverse de l'exposant qui est la 2ème clef publique modulo <math>\(\varphi(n)\)</math>) et donc trouver la clef privée.