Нахождение простых множителей числа

Я пытаюсь найти самый большой простой множитель 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

Вот что я получаю в качестве вывода: 

[5, 7, 13, 29, 65, 145, 377, 1015, 2639]
Таким образом, он хорошо работает для первых четырех простых чисел, но как только он начинает удалять числа, которые не являются простыми, код, кажется, пропускает проверку следующего элемента в списке делителей и продолжает двигаться дальше. Почему он это делает?
3 3
python prime-factoring

3 ответа:

Важная строка: 

primes = divisors

Это не копирует список - primes является тем же списком, что и divisors

Поэтому, когда вы делаете 

primes.remove(elements)

Это то же самое, что: 

divisors.remove(elements)

Путает итерацию через элементы, поэтому кажется, что она пропускает.

3

Он пропускает следующий элемент, потому что после удаления элемента индекс каждого следующего элемента уменьшается на единицу. Я бы попробовал уменьшить a после primes.remove(elements)

0

Проблема заключается в том, что вы удаляете элементы из списка, который в то же время повторяется. Это нарушит итерацию.

Вы могли бы вместо этого сделать

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
0