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

It's either homework or not homework, there is no possible-homework. — kennytm, Aug 27 '10 at 09:36
Have you tried brute-force trial division? (i.e. simply `N % k` for `0 < k < sqrt(N)`) How close is that to being fast enough? — Oliver Charlesworth, Aug 27 '10 at 09:48
@AKGMA "Ok! Please focus on answering the question noon these things!" Lose the attitude, dude!. Have you "focused" yourself before trying to get an answer here? Everybody is just trying to help. — celavek, Aug 27 '10 at 09:51

score 1 · Accepted Answer · edited May 23 '17 at 10:28

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 ;)

edited May 23 '17 at 10:28

Community

1
1

answered Aug 27 '10 at 09:47

Ralph M. Rickenbach

12,893
5
29
49

Thanks! Those were really helpful but yet I can't factorize something like 1008322012 in 0.01s. – Aug 27 '10 at 09:49
Sorry but why do i have to test only to the square root? I don't want to see whether n is prime, I want to factorize n. and indeed there are so many prime numbers less than 500,000,000 – Aug 27 '10 at 09:51
1

@AKGMA: Any factor below sqrt(N) will be paired with another factor above sqrt(N). Finding one is equivalent to finding the other. There aren't that many primes below sqrt(500000000) == 22360. – Oliver Charlesworth Aug 27 '10 at 09:53
@AKGMA - Why only to the square root: if you do not find a factor smaller than the square root, the number is prime and you found your factorization. If you find one, add it to the list of factors (maybe several times) and proceed with the factorization of the remainder. As the remainder is smaller than the starting value n, at least one of its factors will be smaller than its square root (which in turn is smaller than the square root of n), or the remainder is prime. – Ralph M. Rickenbach Aug 27 '10 at 09:59
@Oli Charlesworth: I don't have enough memory for that – Aug 27 '10 at 10:03
@AKGMA: There are only 2502 primes below 22360, so this will take 5kB of storage (or less). If you don't have enough memory for that, then you have some very specific constraints, which you should add to your original question. – Oliver Charlesworth Aug 27 '10 at 10:08

score 0 · Answer 2 · edited May 23 '17 at 11:54

0

Start to study the algorithms.
What is the fastest factorization algorithm?

edited May 23 '17 at 11:54

Community

1
1

answered Aug 27 '10 at 09:49

clyfe

23,695
8
85
109

score 0 · Answer 3 · answered Aug 27 '10 at 09:52

0

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".

answered Aug 27 '10 at 09:52

PhilR

5,375
1
21
27

1

It suffices to store the smallest factor, then divide and repeat until done. – starblue Aug 27 '10 at 19:49

score 0 · Answer 4 · answered Aug 27 '10 at 09:52

0

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

Pollard's rho

answered Aug 27 '10 at 09:52

tchrikch

2,428
1
23
43

score 0 · Answer 5 · answered Aug 27 '10 at 12:58

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.).

Factorizing a number

5 Answers5