phi (n)

int phi(int m)
{
    int ans = m;
    for(int i = 0; i < pr.size() && m >= pr[i]*pr[i]; i++)
    {
        if(m % pr[i] == 0)
        {
            ans /= pr[i];
            ans *= (pr[i] - 1);
            while(m % pr[i] == 0) m /= pr[i];
        }
    }
    if(m > 1) ans = (ans/m)*(m - 1);
    return ans;
}