Euler's totient exactly k times Given n and k, I need to find Euler's totient exactly k times where n and k are very large numbers. Can anyone help with an optimized solution for a large number?

#include &lt;iostream&gt;
using namespace std;

 int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}


int phi(unsigned int n)
{
    unsigned int result = 1;
    for (int i=2; i &lt; n; i++)
        if (gcd(i, n) == 1)
            result++;
    return result;
}

int main() 
{ 
    long n,i,k; 

    cin &gt;&gt;n&gt;&gt;k; 
    long a[n]; 

    for (i=1; i&lt;=k; i++) 
        n = phi(n);

    cout &lt;&lt; n&lt;&lt;endl; 

    return 0; 
    }
Do prime factorization

Your current phi() function is correct but slow.  You would do better by finding the prime factorization of n and using the prime factors to calculate phi.  Your current phi() takes \$O(n)\$ time, but a prime factorization takes \$O(\sqrt n)\$ time.

Stop at one

At some point, if k is large, you will reach n of 1.  At that point you can stop because phi(1) = 1.  Actually if at any point k &gt;= n, the answer should be 1 because phi(n) reduces n by at least 1.