CODEWITHSUNDEEP
pythonprime-factoring
Mburdzy
Mburdzy

Reputation: 35

Finding prime factors of a number

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

Answers (3)

nomis
nomis

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

Logicrat
Logicrat

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

Douglas Leeder
Douglas Leeder

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

Related Questions