MegaAmoonguss MegaAmoonguss - 3 months ago 6
Java Question

What is wrong with this prime factorization code in Java?

I was trying to make a method to do the prime factorization of a number, and it's probably not the most efficient, but I don't see why it shouldn't work.

public static ArrayList<Integer> primeFactorize(int num) {
ArrayList<Integer> primeFactors = new ArrayList<Integer>();

for (int i = 2; i < Math.sqrt((double) num); i++) {
if (isPrime(i) && factor(num).contains(i)) {
primeFactors.add(i);
num /= i;

if (isPrime(num)) {
primeFactors.add(num);
break;
}
i = 2;
}
}
return primeFactors;
}


It calls upon two other methods that I wrote named factor() and isPrime(), which do exactly what you would expect them to (returns an ArrayList of factors and either
true
or
false
depending on if the input is prime, respectively).

I went through the debugger with
num
being 12, and it worked fine for the first loop, where it added 2 to
primeFactors
. However, when it got to the top of the array again with
num
being 6 and
i
being 2, it exited the loop as if
i < Math.sqrt((double) num)
returned
false
.

But that wouldn't make sense, because the square root of 6 is a bit over 2. I also tried
(double) i < Math.sqrt((double) num)
, but it just did the same exact thing.

Can anyone see what I'm missing? Thanks for any replies.

EDIT: Here is my code now, thanks for the help! I know for sure I could make it more efficient, so I might do that later, but for now this is perfect.

public static ArrayList<Integer> primeFactorize(int num) {
ArrayList<Integer> primeFactors = new ArrayList<Integer>();

int i = 2;
while (i < Math.sqrt((double) num)) {
if (isPrime(i) && num % i == 0) {
primeFactors.add(i);
num /= i;

if (isPrime(num)) {
primeFactors.add(num);
break;
}
i = 2;
}
else
i++;
}
return primeFactors;
}

Answer

In your for loop, the i++ section will get called at the end of every loop. So in your code, you set i equal to 2. Then, the loop ends, and adds 1 to i, making it be 3. Then the comparison happens, and 3 is more than sqrt(6), so the loop exits.

If you want i to be 2 in the next iteration, you need to set it to a value so that after the increment operation runs it will be 2, not before; in this case, you should set it to 1. A better solution would be to change your code structure so it's not necessary though. As pointed out by biziclop, a while loop will let you decide whether or not to increment, and will avoid this problem.