2
\$\begingroup\$

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 <iostream>
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 < n; i++)
        if (gcd(i, n) == 1)
            result++;
    return result;
}

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

    cin >>n>>k; 
    long a[n]; 

    for (i=1; i<=k; i++) 
        n = phi(n);

    cout << n<<endl; 

    return 0; 
    }
\$\endgroup\$
6

2 Answers 2

3
\$\begingroup\$

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 >= n, the answer should be 1 because phi(n) reduces n by at least 1.

\$\endgroup\$
1
  • \$\begingroup\$ I modified the code according to your answer. Please check can i improvise it bit more? \$\endgroup\$ Oct 17, 2016 at 4:19
2
\$\begingroup\$
  1. Do not use namespace std; this is bad practice and the sooner you stop it the better.

  2. Use descriptive names. Even for programming challenges, you can actually use variable names that mean something. This makes the code much easier to understand.

  3. Use an stl container in this case most likely std::vector. But more important, what is the purpose of a[n], as you do not use it in the code.

  4. An unsigned int is the same as an unsigned

  5. return 0 is superfluous for modern compilers so you can omit it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.