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