Indicatorul lui Euler

[•AlexCom]

    Am dat peste o problema care spune sa afisez indicatorul lui Euler pentru toate numerele nat mai nici sau egale cu n...Problema nu este deloc complicata , doar ca eu nu inteleg care este treaba cu Indicatorul lui Euler..si ce face acesta.

    Am cautat definitii pe net si am gasit ceva de genul : Indicatorul lui Euler sau funcția lui Euler se notează cu φ(n) (unde n este un număr natural nenul ) și φ(n) reprezintă numărul de numere mai mici decât n și prime cu acesta.
    Dar tot nu imi e destul de clar si nu are cine sa imi explice:D:D

    Poate cineva , va rog , sa imi explice cum sta treaba? si daca se poate sa imi dea si un exemplu pe un numar cu fiecare pas..cred ca asa as intelege...
Multumesc

[•SpiderMan]

Uite pb. asta http://infoarena.ro/problema/fractii e perfecta si http://infoarena.ro/problema/sum. Acest indicator de fapt face ce ai zis tu adineauri. Un numar X este prim cu altul Y daca cmmdc (X, Y) = 1. Spre exemplu, acest lucru merge, dupa cum ziceam la fractii pentru a simplifica fractiile pana ajunge ireductibila. Luam numarul 6 sa zicem. phi(6) o sa fie 2, pe motiv ca 6 este prim cu 1 si cu 5 (Cu 1 pentru ca orice numar este prim cu 1, si respecta conditia cmmdc (6, 1) = 1, si cmmdc (6, 5) = 1), cu 2, 3, 4, cmmdc-ul n-o sa fie 1, ci pe rand 2, 3, 2. Sper c-ai inteles care e treaba cu acest indicator, fa acele probleme pentru clarificare si uite un link unde zice cum sa calculezi acest phi cu ciurului lui eratosthenes.

[•AlexCom]

Mersii mult!! Chiar am inteles , ma apuc acum sa fac pb alea )
Mersii mult inca odata!