Skip to main content
5 of 8
added pythonic loop
DarthGizka
  • 2.8k
  • 1
  • 14
  • 30

Things should be fine if you perform strength reduction on n / num**exp. That not only makes things faster, it also gets rid of the messiness inherent in Python's exponentiation operator (so that you don't have to find out how it actually works under the hood).

In the kth iteration of the inner loop you have a quotient q_k that is equal to n / p**k (i.e. n / num**exp in your code).

To obtain n / p**(k+1) in the next iteration, all you have to do is q_k / p because that makes it (n / p**k) / p, which is equal to n / p**(k+1) as desired. In other words, instead of computing the power of the prime anew and then performing a division, simply divide the old quotient by the prime again.

Here's the complete loop, coded in a more pedestrian language:

static ushort[] primes_up_to_LIMIT = U16.SmallPrimesUpTo(50000).ToArray();

...

uint divisor_count = 1;

foreach (uint prime in primes_up_to_LIMIT)
{
    ulong e = 0;

    for (uint q = n; q >= prime; )
        e += q /= prime; 

    divisor_count = (uint)((divisor_count * (e + 1)) % 1000000007u);
}

return divisor_count;

It isn't very fast - it clocked 0.21 s on SPOJ - but it should show the principle well enough and it can serve as the basis of a more performant solution.

Note: the poor showing of my submission on SPOJ is due to problems inherent in .Net, with the lion's share going to poor input/output performance (and a small part owing to the poor performance of unsigned types in newer versions of .Net).

Unfortunately I do not know enough about Python to tell whether custom input/output code can have the same dramatic effect as it has with .Net... It may be worth looking into. See SPOJ's INTEST and INOUTEST which are useful for tuning one's input/output performance. At CodeChef you can even look at the code of submissions, to see how the fastest timings came about.

Here is an attempt at rending the inner loop in Python (renaming the num from your code to current_prime for clarity, and pr to divisor_count):

q = n
e = 0
while q >= current_prime
    q /= current_prime
    e += q
divisor_count *= (e + 1)
DarthGizka
  • 2.8k
  • 1
  • 14
  • 30