1

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; }
Improve this question
1
  • sqrt(num), not sqrt(i). So with num=12, 6 is greater than sqrt(num) Commented Aug 16, 2016 at 14:40

2 Answers 2

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I knew it had something to do with i++, can't believe I missed that lol, thanks!
General advice: don't use for loops if you manipulate the loop variable from within the loop body. Use while, it'll make your code a lot clearer. Keep for for simple loops between two points.
Why use a functionfactor() ? You just want to know whether the current value of i is a factor of num, so (num%i)==0 will suffice.
I'm not actually sure why I didn't think of that, thanks for that as well lol
3

Since you already accepted an answer I assume your problem is solved. The thing I want to point out is that casting integers to doubles is generally a bad idea if there is another way. Therefore I want to show you the below implementation, which doesn't use floating-point arithmetic. Also I think it's a bad idea to check whether or not num is a prime number, because this slows down the algorithm. Moreover if num % i == 0 evaluates to true, i is always a prime number, thus the isPrime(i) check is superfluous and also slows down your algorithm. 

List <Integer> primeFactors(int n) { List<Integer> factors = new ArrayList<>(); for (int i = 2; i <= n / i; ++i) { while (n % i == 0) { factors.add(i); n /= i ; } } if (n > 1) { factors.add(n); } return factors ; }
Improve this answer

5 Comments

Really nice code, thanks! It's always good to hear about how I could make my code more efficient, considering as a high schooler that's the one thing you don't really learn too much about lol
You are welcome, maybe you (or me) should do a runtime comparison ;). btw up-votes are always welcome :)
i tried to upvote like 5 things but I don't think i have enough reputation yet lol
You could speed up the algorithm by treating factor 2 separately at the start and then changing the loop to step 2 each time from 3: for (int i = 3; i <= n / i; i += 2) That will save testing any even trial factors, except 2.
True, but you can also do every 6 numbers, if you add some more checks. So much clutter do you want to add?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.