I recently started doing exercises on sites such as Code Chef and Project Euler, just for the fun of it. On the latter I was attempting Problem 3: What is the largest prime factor of the number 600851475143?
When calling the method below with the given number, it takes a really long time for an output to be generated. Ultimately, the code throws an ArithmeticException (division by zero) coming from line 7 according to the stack trace. But I don't understand why that is. Could someone help me out?
Here's a problem that beginner programmers often have: They believe that their program does what they meant it to do. Then when an unexpected error message appears, it's hard to stop believing that.
Whereas as an outsider who didn't write the code, I say "Okay, at line 7 there's a division by zero. Well, line 7 doesn't do much except find something modulo i, so therefore i must be zero."
Well, okay, maybe you did get that far. (But you didn't say so.) So how does i get to be zero? That's the question to be asked.
You declared i to be an int value, and an int value can only contain numbers which are less than 4,294,967,296. You can count to that number by adding 1, and when you get there the count rolls over and goes to -4,294,967,296. If you carry on adding 1 for a while longer then the count eventually gets back to zero. And then your program crashes.
Notice that the number you used as input is about 600 billion, whereas an int value can only hold numbers up to about 4 billion. You could change your loop to use a double value rather than an int value, and then your program would probably not crash. But it would take about 100 times as long to run as your posted version did before it crashed. You may end up with a solution to Problem 3 but there must be faster ways.
Thanks for the insight, Paul. It is much appreciated. I am familiar with the concept of overflow, but i failed to make the link. I did not understand why i could ever be zero, but now I do.
It is indeed so that once you believe your code is performing a certain task, it is not easy to "re-evaluate" your code in a critical way. I also did not know how to start debugging it - given the large value of the input number. I did test it with a smaller number and then the code did not fall apart.
I am sure that the algorithm could be optimised in more ways than one, I am indeed a beginner.