寻找一个数的质因数

Question

我正在尝试找到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]

对于前四个质数，这段代码运行良好。但一旦它开始除去不是质数的数字，它似乎跳过了检查除数列表中的下一个元素，并继续向下扫描。为什么会这样呢？

- Mburdzy

Answer 1

重要的一行是：

primes = divisors

这并不是复制列表 - primes 和 divisors 是同一个列表。

因此，当您执行以下操作时：

primes.remove(elements)

这与以下内容相同:

divisors.remove(elements)

混淆了元素的迭代，这就是为什么它似乎会跳过的原因。

- Douglas Leeder

---

非常感谢！运行得非常完美！ - Mburdzy

Answer 2

问题在于您正在从同时正在迭代的列表中删除元素。 这将会中断迭代。

相反，您可以这样做

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

- nomis

Answer 3

它跳过了下一个元素，因为一旦你删除一个元素，每个后续元素的索引都会减少一个。我建议在 primes.remove(elements) 之后将 a 减一。

- Logicrat