2

I am trying to find all the prime numbers in a given list. I am not sure why this code is not working. I tried doing it with flags as well. Thanks for your help. 

def prime_factor(n):  
for i in n:
    for j in range(2,i):
        if i%j == 0:
            n.remove(i)
            break
return n  
prime_factor([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])

Output : [1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19]

Neelotpal Nauriyal
  • 17
  • 5

4 Answers4

1

You should not modify the list you are iterating over.

If you modify a copy of a list and return that the problem is fixed.

from math import sqrt

def prime_factor(n):
    r = n[:]
    for i in n:
        if i == 1:
            r.remove(i)
            continue
        for j in range(2,int(sqrt(i))):
            if i%j == 0:
                r.remove(i)
                break
    return r

prime_factor([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])

Output:

[2, 3, 5, 7, 11, 13, 17, 19]

I also added a check for 1, which is not prime.

Finally, it is not necessary to search past sqrt(i), since if a larger number divides i you will have already seen one of the other factors.

Imran
  • 12,950
  • 8
  • 64
  • 79
1

You can create a variable flag and append numbers in a new list. In that way it will work properly. Check the code below:

def prime_factor(n):
    prime = []
    for i in n:
        flag = 0
        if i==1:
            flag=1
        for j in range(2,i):
            if i%j == 0:
                flag = 1
                break
        if flag ==0:
            prime.append(i)            
    return prime

Input:

prime_factor([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])

Output:

[2, 3, 5, 7, 11, 13, 17, 19]
Sumit S Chawla
  • 3,180
  • 1
  • 14
  • 33
0

Removing items while iterating over a list causes a few problems.
What your code does is skip checking every item after a non-prime.
To be more specific, it only checks: 1, 2, 3, 4, 6, 8, 10, 12, 14, 16, 18, 20.
I suggest you iterate over a copy of the list instead.

See these related questions.

yushi
  • 185
  • 1
  • 11
0

When you call the remove() method it removes the mentioned item from list and shift all the other elements after that to the left to fill in the gap.

s = [1, 2, 3, 4, 5]
s.remove(3)

will give you

s = [1, 2, 4, 5]

And you probably know all that.

The problem here is that the list n is constantly getting modified whenever i%j == 0, so the for loop mistakenly jumps over list elements. The loop has an internal counter of some sort which keeps track of which index of the iterable it is currently on. Here, when the control flow reaches the for loop after a remove() is performed the loop just naturally goes to the next index value, which leads to skipping the next value on the list.

Deepak Mecheri
  • 13
  • 4