Number of divisiors upto 10^6

Question

I have been trying to solve this problem.

http://www.spoj.com/problems/DIV/

for calcuating interger factors, I tried two ways

first: normal sqrt(i) iteration.

int divCount = 2;
            for (int j = 2; j * j <= i ; ++j) {
                if( i % j == 0) {
                        if( i / j == j )
                            divCount += 1;
                        else
                            divCount += 2;
                    }
            }

second: Using prime factorization (primes - sieve)

for(int j = 0; copy != 1; ++j){
                int count = 0;
                while(copy % primes.get(j) == 0){
                    copy /= primes.get(j);
                    ++count;
                }
                divCount *= ( count + 1);}

While the output is correct, I am getting TLE. Any more optimization can be done? Please help. Thanks

Answer 1

You're solving the problem from the wrong end. For any number

  X = p1^a1 * p2^a2 * ... * pn^an // p1..pn are prime

  d(X) = (a1 + 1)*(a2 + 1)* ... *(an + 1)

For instance

  50 = 4 * 25 = 2^2 * 5^2
  d(50) = (1 + 2) * (1 + 2) = 9

  99 = 3^2 * 11^1
  d(99) = (2 + 1) * (1 + 1) = 6

So far so good you need to generate all the numbers such that

   X = p1^a1 * p2^a2 <= 1e6

such that

  (a1 + 1) is prime
  (a2 + 1) is prime

having a table of prime numbers from 1 to 1e6 it's a milliseconds task

Answer 2

It is possible to solve this problem without doing any factoring. All you need is a sieve.

Instead of a traditional Sieve of Eratosthenes that consists of bits (representing either prime or composite) arrange your sieve so each element of the array is a pointer to an initially-null list of factors. Then visit each element of the array, as you would with the Sieve of Eratosthenes. If the element is a non-null list, it is composite, so skip it. Otherwise, for each element and for each of its powers less than the limit, add the element to each multiple of the power. At the end of this process you will have a list of prime factors of the number. That wasn't very clear, so let me give an example for the numbers up to 20. Here's the array, initially empty:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

Now we sieve by 2, adding 2 to each of its multiples:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2

Since we also sieve by powers, we add 2 to each multiple of 4:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2
       2           2           2           2           2

And likewise, by each multiple of 8 and 16:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2
       2           2           2           2           2
                   2                       2
                                           2

Now we're finished with 2, so we go to the next number, 3. The entry for 3 is null, so we sieve by 3 and its power 9:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2
       2           2           2           2           2
                   2                       2
                                           2
    3        3        3        3        3        3
                      3                          3

Then we sieve by 5, 7, 11, 13, 17 and 19:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
 2     2     2     2     2     2     2     2     2     2
       2           2           2           2           2
                   2                       2
                                           2
    3        3        3        3        3        3
                      3                          3
          5              5              5              5
                7                    7
                            11
                                 13
                                             17
                                                   19

Now we have a list of all the prime factors of all the numbers less than the limit, computed by sieving rather than factoring. It's easy then to calculate the number of divisors by scanning the lists; count the number of occurrences of each factor in the list, add 1 to each total, and multiply the results. For instance, 12 has 2 factors of 2 and 1 factor of 3, so take (2+1) * (1+1) = 3 * 2 = 6, and indeed 12 has 6 factors: 1, 2, 3, 4, 6 and 12.

The final step is to check if the number of divisors has exactly two factors. That's easy: just look at the list of prime divisors and count them.

Thus, you have solved the problem without doing any factoring. That ought to be very fast, just a little bit slower than a traditional Sieve of Eratosthenes and very much faster than factoring each number to compute the number of divisors.

The only potential problem is space consumption for the lists of prime factors. But you shouldn't worry too much about that; the largest list will have only 19 factors (since the smallest factor is 2, and 2^20 is greater than your limit), and 78498 of the lists will have only a single factor (the primes less than a million).

Answer 3

Even though the above mentioned problem doesn't require calculating number of divisors, It still can be solved by calculating d(N) (divisors of N) within the time limit (0.07s).

The idea is to pretty simple. Keep track of smallest prime factor f(N) of every number. This can be done by standard prime sieve. Now, for every number i keep dividing it by f(i) and increment the count till i = 1. You now have set of prime counts for each number i.

int d[MAX], f[MAX];

void sieve() {
  for (int i = 2; i < MAX; i++) {
    if (!f[i]) {
      f[i] = i;

      for (int j = i * 2; j < MAX; j += i) {
        if (!f[j]) f[j] = i;
      }
    }

    d[i] = 1;
  }


  for (int i = 1; i < MAX; i++) {
    int k = i;

    while (k != 1) {
      int s = 0, fk = f[k];

      while (k % fk == 0) {
        k /= fk; s++;
      }

      d[i] *= (s + 1);
    }
  }
}

Once, d(N) is figured out, rest of the problem becomes much simpler. Keeping a smallest prime factor of every number also helps to solve lots of other problems.