4
\$\begingroup\$

In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Given an integer n (1 ≤ n ≤ 106), compute the value of the totient φ.

For the code written below, this is giving TLE. How i can optimize this code or should i prefer some other language for this problem. Link of the problem at spoj

test = int(input())
for t in range(test):
    n = int(input())
    result = n
    i = 2
    while i*i <= n :
        if n %i == 0:
            while n%i == 0 :
                n /= i
            result -=result/i
        i +=1
    if n > 1:
        result -= result/n
    print(int(result))
\$\endgroup\$
4
\$\begingroup\$

The way I would approach this problem is to find the prime factorization of n, and then use Euler's formula which says:

$$\varphi(n) = n \prod_{p|n}\left(1 - \frac{1}{p}\right)$$

The easiest way to do this is to find the prime factorization of n (which you are basically already doing), but store each distinct prime factor in a list. Once you are done, compute this formula for the primes, and you should have your answer fairly quickly.

\$\endgroup\$
  • \$\begingroup\$ How did you use LaTex? I looked it up, but couldn't figure out how. \$\endgroup\$ – Oscar Smith Aug 1 '16 at 18:36
  • \$\begingroup\$ For MathJax, use $$ display math $$ or \$ inline math \$. \$\endgroup\$ – 200_success Aug 1 '16 at 19:05
4
\$\begingroup\$

This is a problem about number theory, dealing entirely with integers. You should not be using floating-point division (the / operator), but rather integer division (the // operator).

I also suggest organizing your code properly (writing a useful mathematical function that accepts and returns an integer). Also, it would be nice to use whitespace consistently (conforming to PEP 8).

def totient(n):
    result = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
        i += 1
    if n > 1:
        result -= result // n
    return result

for _ in range(int(input())):
    print(totient(int(input())))
\$\endgroup\$
  • \$\begingroup\$ Thanks for the code, I learnt few things. Still getting TLE for your code, and you have missed a small bracket , this would be nice if you correct it. I upvoted your answer, but doesn't have enough reputation right now. Thanks for your help. \$\endgroup\$ – sarvajeetsuman Aug 1 '16 at 19:02
0
\$\begingroup\$

200_success's solution cannot be much improved on, except by computing the handful of primes up to 1000 (i.e. sqrt(1,000,000)) up front to reduce the number of trial divisions that need to be performed.

I find it surprising though that this solution should TLE. On my aging Lynnfield a C# rendering of it (with pre-sieved primes) takes 4 ms for 20,000 random numbers in the target range, and 10 ms for 20,000 random primes from that range...

In a compiled language like C# there are additional optimisations that could be applied, like treating the prime 2 separately (elementary bit ops instead of division), or computing the modular inverses of above-mentioned small primes so that a divisibility test reduces to a multiplication followed by a comparison. However, in an interpreted language like Python there is little to be gained from that, because the interpreter overhead dwarfs the cost of these elementary operations.

Be that as it may, the high number of queries makes up-front computation of a phi table a viable alternative here. A suitable algorithm is discussed in Linear time Euler's Totient Function calculation. It uses the multiplicative properties of phi() to compute all values at little more than one division per result, by enumerating the target range in the form of least factor decompositions. It is worth keeping in mind because it can easily be adapted to handle other multiplicative functions.

Since my code in that topic is an early draft at early levels of understanding, here is a more mature rendering that I used my SPOJ submission (0.03 s):

static uint[] compute_phi_table (uint limit = 1000000)
{
    var phi = new uint[limit + 1];

    phi[1] = 1;

    var small_primes = new System.Collections.Generic.List<uint>();

    // For each number in the target range, the outer loop has to supply what
    // remains after dividing by the smallest factor; hence we have to go up to N/2.

    uint n = 2, small_prime_limit = (uint)Math.Sqrt(limit);

    for (uint e = limit / 2; n <= e; ++n)
    {
        uint phi_n = phi[n];

        if (phi_n == 0)
        {
            phi_n = phi[n] = n - 1;

            if (n <= small_prime_limit)
            {
                small_primes.Add(n);
            }
        }

        foreach (uint current_prime in small_primes)
        {
            uint nth_multiple = n * current_prime;

            if (nth_multiple > limit)
                break;

            if (n % current_prime != 0)  // current_prime is not a factor of n
            {
                phi[nth_multiple] = phi_n * (current_prime - 1);
            }
            else // current_prime is a factor of n (the smallest, to be precise)
            {
                phi[nth_multiple] = phi_n * current_prime;
                break;
            }
        }
    }

    // process the primes in the rest of the range up to N (stepping mod 6)

    n += 1 - (n & 1);
    n += n % 3 == 0 ? 2u : 0u;

    for (uint d = (3 - n % 3) * 2; n <= limit; n += d, d ^= 6)
        if (phi[n] == 0)
            phi[n] = n - 1;

    return phi;
}

The last step - the loop that replaces null entries with n - 1 - can be skipped for SPOJ ETF, if null values retrieved from the table are treated accordingly.

Note, however, that this solution is slower than the earlier one. On my aged PC it takes 17 ms for computing the table up to 10^6, whereas factorisation with pre-computed primes can answer 20,000 random point queries in 4 ms - a mere fraction.

In other words, it seems that 200_success's solution combined with pre-computing a list of primes up to 1,000 is already the best that can be done in Python...

The table-based solution isn't very competitive in this particular instance (especially in Python, with its interpreter overhead), but in similar challenges it might well be. So it is worth keeping it in mind, especially as other multiplicative functions can be handled in the same fashion.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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