I'm trying to find all of the prime factors for a given number. The following code achieves this:
However, if I remove the boolean test isPrime, as below, I get additional numbers after the highest prime factor.
I can't work out why this should be. From my understanding, the divisor only gets added to the list of primes if the loop doesn't break (which, with the boolean test would be true anyway). What am I not understanding?
The break; is breaking out of the inner loop, not the outer loop.
Perhaps it will be clearer if I walk you through the code -
The original code assumes any factor is initially prime. That’s the initial value of the isPrime boolean flag. The purpose of the inner for loop is to see if that factor is not a prime number. If the factor is divisible, the isPrime flag is set to false and there is no reason to continue to check, so the inner loop is exited early with the break;. That factor will not be added to the primes collection in line 14 as isPrime == false.
If you remove the isPrime boolean, you are no longer collecting just the prime factors. Now, the inner for loop really doesn’t do anything. It simply finds out that a number is divisible, breaks out of the inner loop and moves to the line that adds to the collection the factors. Since there is no isPrime flag condition saying add only prime factors, any number that gets to this point is added.
For example, if you enter 100 as an input-
Initial code returns: [2, 5]
Modified code returns: [2, 4, 5, 10]
4 & 10 are not prime numbers and shouldn't be part of the collection.
Thanks for that Chris. When I wrote the function initially it made perfect sense why I used the boolean test. I came back to it later in the day and could not understand at all why I had done it. It's helped clarify how break works for me, as I thought it broke out of all the loops and started the cycle again. Good luck on the quest for cows!
Post by:autobot
Don't touch me. And dont' touch this tiny ad:
a bit of art, as a gift, that will fit in a stocking