Algorithm optimization

Question

Here is a link to the problem.

The problem defines the number of solutions of the Diophantine equation of the form 1 / x + 1 / y = 1 / z (where z = n! ). A permutation of this equation clearly indicates that the answer is the number of factors z ² .

Thus, the problem boils down to finding the number of factors n! ² (n factorial squared).

My algorithm is as follows

1. Create a boolean lookup table for all primes <= n using the Sieve of Eratosthenes algorithm.
2. Go through all the primes P <= n and find its exponent in n! , I did this using a step by step formula. Let the exponent be K , then the exponent P is n! ² will be 2K .
3. Using step 2, calculate the number of factors using the standard formula.

For the worst case of entering n = 10 ^6, my code c gives an answer of 0.056 s. I guess the complexity is not much more than O (n lg n) . But when I sent the code to the site, I was able to go through only 3/15 test cases with a verdict on the rest, because the time limit was exceeded.

I need some tips to optimize this algorithm.

Code so far:

#include <stdio.h> #include <string.h> #define ULL unsigned long long int #define MAXN 1000010 #define MOD 1000007 int isPrime[MAXN]; ULL solve(int N) { int i, j, f; ULL res = 1; memset(isPrime, 1, MAXN * sizeof(int)); isPrime[0] = isPrime[1] = 0; for (i = 2; i * i <= N; ++i) if (isPrime[i]) for (j = i * i; j <= N; j += i) isPrime[j] = 0; for (i = 2; i <= N; ++i) { if (isPrime[i]) { for (j = i, f = 0; j <= N; j *= i) f += N / j; f = ((f << 1) + 1) % MOD; res = (res * f) % MOD; } } return res % MOD; } int main() { int N; scanf("%d", &N); printf("%llu\n", solve(N)); return 0; } 

Answer 1

There is an int overflow here:

 for (j = i, f = 0; j <= N; j *= i) 

If 46340 < i < 65536 and for many large i , in the second iteration j will be negative if the overflow wraps around (this behavior is undefined, so anything can happen).

Replace it with e.g.

 for(j = N / i, f = 0; j > 0; j /= i) { f += j; } 

However, it is unlikely that additional iterations due to overflow will cause "time out", which is likely to lead to incorrect results.

So, general advice

• The sieve is only odd numbers, it is also possible to exclude a multiple of 3 from the sieve. Eliminating odd numbers from the sieve grossly reduces the time required for the gratings.
• Do not use integer int for flags, use bits or at least char s. This gives better cache locality and further acceleration.