2

I have here a simple algorithm for factorizing. 

void primeFactor(int number){
    if (number == 1)return;

    int x = 2;
    while (number%x != 0)x++;

    cout << x << endl;
    primeFactor(number / x);
}

It works fine for small numbers, but when ever I enter a big number like 809800987876, I get a -1 after about 3 factors.

So here's sample output for 809800987876.

> 2 2 486957767
> -1

How can I fix this?

Cœur
  • 37,241
  • 25
  • 195
  • 267
JohnCena7070
  • 23
  • 3
  • 1
    Please do not change your question to a different question. If you have a new question then ask a new question using the "Ask Question" link – NathanOliver Dec 02 '15 at 14:25

1 Answers1

2

You are overflowing the int. On a typical system the maximum value of an int is 2147483647. 809800987876 is larger than that so it overflows. You can use a long long which has at least a max of 9223372036854775807.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
  • 2
    If only my bank account had the same problem – EaziLuizi Dec 02 '15 at 14:16
  • Thank you, would you have anything to comment about my algorithm ? could it be more efficient ? – JohnCena7070 Dec 02 '15 at 14:16
  • also wouldn't it be better if i used _int64 instead ? – JohnCena7070 Dec 02 '15 at 14:18
  • 1
    @JohnCena7070 Well I would not recursion to solve this. There is a nice answer [here(http://stackoverflow.com/a/11924315/4342498) that shows how to do it iteratively and has some more information for even better approaches. As to your second question that is more of a style point. a long long is guaranteed to be at least 64 bits. – NathanOliver Dec 02 '15 at 14:23
  • 1
    @JohnCena7070 there are both simple improvements you can make to trial division (for example, other than 2 you don't have to test any even numbers, and you only have to go up to and including the sqrt of the input), and other algorithms that are faster (but more complicated). – harold Dec 02 '15 at 14:28