2

I'm hoping there is an easy solution to this. I can't seem to wrap my head around why this occurs. Everything online suggests this should not be the behavior I'm seeing from Python 3.8.

I'm working on Problem 3 on projecteuler.net. You have to find the prime factorization of a huge number, and multiply them altogether.

My idea was to first find every factor less than half of the original number (unrelated, but this works mathematically and saves time). Then I would simply iterate through the list of factors to remove any that weren't prime.

When I get to any factor that isn't prime, I use a break to get out of the nested loop which checks for and removes the nonprime ones, but it then proceeds to skip checking the next factor entirely as well. Essentially, it's behaving like a continue statement on the outer loop.

I've tried many modifications, including a try and except, but nothing will stop the break from skipping over the next factor.

Here is the code with extra print functions called for debugging purposes:

import math as m
def prime_factor(n):
    factors = []
    
    for i in range(1,m.ceil(n/2)):
        if n % i == 0:
            factors.append(i)
            
    print(factors)
    for num in factors:
        print('******', num, '******')
            for i in range(2, num):
                if num % i == 0:
                    print('NOT PRIME', num, 'NOT PRIME')
                    factors.remove(num)
                    break
    print(factors)
    return factors


prime_factors = prime_factor(100)

Here is the output of that code if run:

[1, 2, 4, 5, 10, 20, 25]
****** 1 ******
****** 2 ******
****** 4 ******
NOT PRIME 4 NOT PRIME
****** 10 ******
NOT PRIME 10 NOT PRIME
****** 25 ******
NOT PRIME 25 NOT PRIME
[1, 2, 5, 20]

First list is of all factors. Then, it's supposed to check each factor, but since 10 was found to not be a factor, the inner loop is broken, and then 20 is skipped in the outer loop.

I really hope somebody finds this problem interesting enough to help me solve it, because I'm at a loss besides just trying an entirely different approach altogether.

Thanks for any and all help.

John Hunt
  • 33
  • 3
  • Does this answer your question? [How to remove items from a list while iterating?](https://stackoverflow.com/questions/1207406/how-to-remove-items-from-a-list-while-iterating) – DYZ Jul 01 '21 at 04:50

2 Answers2

0

You are destructively modifying the list that you are iterating over which is not a good idea. If you refactor using list comprehension which is non destructive by nature, you have clearer code and the problem goes away. However, to immediately correct the problem, wrap list around your factors list - for num in list(factors):.

Paul Whipp
  • 16,028
  • 4
  • 42
  • 54
  • I see what you mean regarding the destruction. I appreciate it. Swapping the code with `for num in list(factors):` solution worked, but your answer immediately made me think about another solution using a cloned list of factors. I first add `num` to `prime_factors`, then inside the nested loop, if it's not prime, I remove it again. I'm sure it's not the most optimized solution, but it works, and is probably better than modifying the list I'm iterating over. Thanks again! – John Hunt Jul 01 '21 at 09:05
0

I can see the problem is the remove function that you have specified.
Consider this

before remove: [1, 2, 4, 10, 20, 25] num : 4
after remove: [1, 2, 10, 20, 25] num : 4

You can see that after removing 4 , 10 takes it's index( in this case 2) value so for the next iteration it goes to 20 not 10.

Deepak velu
  • 154
  • 9
  • Thank you. Both of these responses helped me see the big picture. I decided to go another route that I realized immediately after reading both of these, where I used a second list to add and remove factors list instead of the one I'm iterating over. – John Hunt Jul 01 '21 at 09:08