[Python] Fonction indicatrice d'Euler

[Charmander]

Bonjour, je cherche de l'aide pour programmer sur Python la fonction P indicatrice d'Euler. J'y arrive par la méthode naïve en testant tous les nombres inférieurs à n mais je souhaite obtenir un programme qui marche pour les grands nombres.

Il m'est indiqué d'ailleurs d'utiliser la relation:

avec la somme portant sur les diviseurs positifs de n.

Même si vous ne savez pas comment programmer en Python, savez-vous comment calculer facilement P(n) à l'aide de cette relation ? Merci d'avance !

[fatal_error]

slt,

si on te dit d'utiliser le résultat, alors tu remarques que les diviseurs de n, c'est 1,d_1,...,d_k,n
Tu as donc P(1)+...+P(d_k)+P(n)=n
d'ou P(n)=n-P(1)-...-P(d_k)

Tu n'as plus qu'à faire un inventaire des diviseurs d de n, et pour chacun de ses diviseurs, calculer P(d).
La fonction récursive ressemble à qqch comme

Code: Tout sélectionner

function P(n)
 if n == 1; return 1;
 var allDivisorOfN = getDivisorOfN(n)
 var result = n
 forall allDivisorOfN as divisorOfN
   result -= P(divisorOfN)
 endforall
 return result;
end

Bien sûr, tu devrais stocker tes résultats intermédiaires dans un tableau, (memoization)

[Charmander]

D'accord, merci beaucoup ! :)