Phi

int Phi(int n)
{
    int d;
    unsigned long long int nrp=n,prod=1;
    if(n%2==0)
    {
        while(n%2==0)
            n/=2;
        nrp*=(2-1),prod*=2;
    }
    d=3;
    while(n>1)
    {
        if(n%d==0)
        {
            while(n%d==0)
                n/=d;
            nrp*=d-1,prod*=d;
        }
        else
            d+=2;
        if(n>1&&d*d>n)
        {
            nrp*=n-1,prod*=n;
            break;
        }
    }
    return (int) (nrp/prod);
}