MegaAmoonguss - 10 months ago 43

Java Question

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`

`false`

I went through the debugger with

`num`

`primeFactors`

`num`

`i`

`i < Math.sqrt((double) num)`

`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)`

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.

Source (Stackoverflow)