A small note first, please do not double-space all lines in code, it just makes it harder to read, rather than easier.
Integer overflow
Using an int
primitive type for i
and j
is causing the number to go through integer overflow and go back to its minimum value -2,147,483,648 (or \$-2^{31}\$), once it exceeds the maximum value 2,147,483,647 (or \$2^{31}-1\$), then finally all the way back from there to \$0\$, resulting in a java.lang.ArithmeticException: divide by zero
. To correct this, use a long
type for the iterators instead:
// this is to see if num is factorable
for (long i = 2; i < num; i++) {
//if i is a factor, check if its prime
if (num % i == 0) {
for (long j = 2; j < i; j++) {
Algorithm
With the above problem fixed, we can now see that the algorithm you use has a few problems. Given the number \$n = 600851475143\$
It checks every number \$i\$ in the set \$[2,3,4, \ldots, n-1]\$ to see if it is a factor of \$n\$.
For each \$i\$, it then checks every number \$j\$ in the set \$[i, i+1, i+2,\ldots, n-2]\$ to see if it is prime.
It returns each number that matches both criteria, e.g., 71, 839, 1471 and finally the answer, and then it just keeps on going until \$i = 600851475143 - 1\$, which takes a very long time.
The "right" algorithm is very simple, and involves no primality testing. I left an explanation of it in the code comments. This finds the right answer in less than 1 second. There would be other ways to improve it to be more Java/object-oriented, but for the sake of a math exercise like this it should do pretty nicely. Here is a live demo as well.
class LargestPrimeFactor {
public static void main(String[] args) {
long N = 600851475143L;
// First, start from the maximum number and divide by 2
// until you can no longer divide evenly by 2, i.e., the number is odd
while (N % 2 == 0) {
// in the case of 600851475143 this will be skipped entirely since it is an odd number,
// but for the sake of generality we will keep it so it can be used on any number
N /= 2;
}
// the next prime number is 3, and all prime numbers from there are odd numbers,
// so we can safely just add 2 to the factor each time and only test for odd numbers
// note that this has a small inefficiency in that it will also test for a few non-prime odd numbers
// like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
for (long factor = 3; factor < N; factor += 2) {
// if N is evenly divisible by the factor, then we just divide it, and we keep going
// until N can no longer be divided by a number smaller than itself,
// in other words, until N is a prime number
while (N % factor == 0 && factor < N) {
N /= factor;
}
}
System.out.println("The answer is " + N);
}
}
int i
andint j
should belong i
andlong j
respectively. (More than believe, I know it to be true.) You're falling into an integer overflow issue, as the valuenum
is larger than the max value of anint
, so,i
wraps back around to 0 and throws an exception. \$\endgroup\$i
overflowed the maximum integer. It sounds like the code is not working correctly. Can you please clarify? \$\endgroup\$