void work()
{
    int t = 0;
    p[1] = 1;
    for(int i = 2; i <= n; i ++ )
        {
            if(!v[i])
            {
               prime[++t] = i;
               p[i] = i-1;
            }
            for(int j = 1; prime[j] * i <= n; j ++ )
               {
                    v[prime[j] * i] = 1;
                    if(i % prime[j] == 0)
                    {
                        p[prime[j] * i] = p[i] * prime[j]; 
                        break;
                    }
                    else
                    {
                        p[prime[j] * i] = (prime[j] - 1) * p[i]; 
                    }
               }
        }
}