Different results from for-loop and while-loop for prime factorization in Python 3

Question

I have written a function that returns the prime factors of a given integer. For the cases I tested, it seems to work alright. Here is the original function.

def prime_factors_2(num: int) -> set:
    factors = []
    while num % 2 == 0:
        factors.append(2)
        num //= 2
    i = 3
    while i <= int(sqrt(num)) + 1:
        if num % i == 0:
            factors.append(i)
            num //= i
        else:
            i += 2
    if num != 1:
        factors.append(num)
    return set(factors)
    # num = 867844
    # Output = {601, 2, 19}

While messing around with the code, I tried to implement the same but with a for loop instead of a while loop (as I prefer to use a for loop when counting is involved). This is the code for the second function.

def prime_factors_1(num: int) -> set:
    factors = []
    while num % 2 == 0:
        factors.append(2)
        num //= 2
    for i in range(3, int(sqrt(num)) + 1, 2):
        if num % i == 0:
            factors.append(i)
            num //= i
            print(num)
    if num != 1:
        factors.append(num)
    return set(factors)
    # num = 867844
    # Output = {2, 19, 11419}

For some reason, it no longer factors the 11419 into 601 and 19. Are both the loops not equivalent? Or am I making some mistake while translating the while loop to a for loop? I know that there is no practical difference between the two loops in this case, but I want to know this out of pure curiosity.

question from:https://stackoverflow.com/questions/65833201/different-results-from-for-loop-and-while-loop-for-prime-factorization-in-python

Answer 1

Problem is that in your "while loop", you are incrementing the value of "i" by 2 only when the "if" condition is not satisfied, but in the case of "for loop", i is getting incremented by 2 in each iteration.

So if you'll do something like:

while i <= int(sqrt(num)) + 1:
    if num % i == 0:
        factors.append(i)
        num //= i
    i += 2

Then the prime_factors_2 function would also result in the same answer as the prime_factors_1 function