Factorizing a number

Question

I've got a number which is less than 500,000,000 and I want to factorize it in an efficient way. What algorithm do you suggest? Note: I have a time limit of 0.01 sec!

I've just written this C++ code but it's absolutely awful!

void factorize(int x,vector<doubly> &factors)
{
  for(int i=2;i<=x;i++)
    {
      if(x%i==0)
    {
      doubly a;
      a.number=i;
      a.power=0;
      while(x%i==0)
        {
          a.power++;
          x/=i;
        }
      factors.push_back(a);
    }
    }
}

and doubly is something like this:

struct doubly
{
  int number;
  int power;
//and some functions!!

};

just another point: I know that n is not a prime

Answer 1

As you might know, factorization is a hard problem. You might also know that you only have to test divisibility with primes. A small, but well known hint: You only have to test up to the square root of n. I leave the reasoning to you.

Look at the sieve of Eratosthenes. And maybe you find a hint in these questions and answers? How about that one?

If you want to make this faster even - without the full trade of in space/time of this answer - calculate all prime numbers up to square root of 500,000,000 in advance and put them into an array. Obviously this is broken when the upper limit grows ;)

Answer 2

Start to study the algorithms.
http://stackoverflow.com/questions/2267146/what-is-the-fastest-factorization-algorithm

Answer 3

Factorize all the integers up to 500,000,000 in advance (doesn't matter how) and store the factors in a database or fixed-length record format. Your lookup will be fast, and the database ought to fit onto a modern PC.

This is one end of the time/space tradeoff, but you didn't say what you're trying to optimize for.

Alternatively, look at the algorithm for GNU coreutils "factor".

Answer 4

You may try Pollard's rho heuristic, it's suitable for complex numbers with relatively small divisors:

Pollard's rho

Answer 5

If this is a homework assignment, I believe you should re-read your lecture material.

Anyway, you know your number is composite and very small, that's fine.

For a naive trial-division with all numbers, you need sqrt(500000000) tests at most - that's about 22360 times for worst-case. You can obviously skip even numbers since they're divisible with 2 (check that first). So then this becomes 11180 divisions for 0.01 s. If your computer can do 1.1 M divisions per second then you can just use the naive approach.

Or, you can make a list of primes off-line, up to sqrt(500M) and then trial-try each of those. This will cut down on divisions some more.

Or, if the factors are not too far away from each other, you could try Fermat's method.

If these won't work, you can try to use Pollard's rho and others.

Or, if this is not homework, restate the problem to work around the limitations (as some have suggested, can you precompute the factored numbers beforehand etc.).