Reputation: 35
I'm trying to find the largest prime factor of 13195:
def problem3():
divisors = []
primes = []
num = 13195
for a in range(2, num):
if num % a == 0:
divisors.append(a)
print divisors #This is the list of all divisors of the number
// At this point divisors looks like:
// [5, 7, 13, 29, 35, 65, 91, 145, 203, 377, 455, 1015, 1885, 2639]
print ""
primes = divisors
for elements in divisors:
for a in range(2,elements):
if elements % a == 0:
primes.remove(elements)
print divisors
break
print primes
Here's what I get as output:
[5, 7, 13, 29, 65, 145, 377, 1015, 2639]
So it works well for the first four primes, but once it starts removing numbers that aren't primes, the code seems to skip checking the next element in the divisors list, and continues moving on. Why does it do this?
Upvotes: 3
Views: 205
Reputation: 2715
The problem is that you are removing elements from the list that is at the same time being iterated over. It will break the iteration.
You could instead do
for elements in divisors:
isPrime = True
for a in range(2,int(math.sqrt(elements) + 1)):
if elements % a == 0:
isPrime = False
break
if isPrime:
primes.append(elements)
print primes
Upvotes: 0
Reputation: 4468
It's skipping the next element because once you remove an element, the index of each following element is reduced by one. I would try decrementing a
after primes.remove(elements)
Upvotes: 0
Reputation: 53285
The important line is:
primes = divisors
This does not copy the list - primes
is the same list as divisors
So when you do
primes.remove(elements)
It is the same as:
divisors.remove(elements)
The messes up the iteration through elements, which is why it seems to skip.
Upvotes: 3