MegaAmoonguss - 2 months ago 4
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)) {
num /= i;

if (isPrime(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) {
num /= i;

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

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.