FUNCTII_indic_lui_Euler-SI_cmmdc

int phi(int n) /// Functia Totient (indicatorul lui Euler)
{ /// Intoarce numarul de numere naturale mai mici decat n si prime cu n
    float rezultat=n;   /// Initializa rezultat cu n
    for(int p=2;p*p<=n;++p) /// Consideram toti factorii primi ai n si pentru fiecare factor prim p, multiplicam rezultatul cu (1-1/p)
    {
        if(n%p==0) /// Verificam daca p este factor prim
        {
            while (n%p==0) /// Daca da, actualizam n si rezultatul
                n/=p;
            rezultat*=(1.0-(1.0/(float) p));
        }
    }
    if (n>1) /// Daca n are un factor mai mare decat sqrt(n) (poate exista cel mult un astfel de factor prim)
        rezultat*=(1.0-(1.0/(float) n));
    return (int)rezultat;
}

int cmmdc(int a,int b)
{
    int r=a%b;
    while(r!=0)
        a=b,b=r,r=a%b;
    return b;
}