python - 欧拉项目 Q #3 Python

Question

我真的很想通过解决欧拉项目问题来提高我的数学/编码/解决问题的能力，但我在第三个问题上有点卡住了。问题是“13195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少？”

这是迄今为止我的代码

import math

def isPrime(n):
   if n > 1:
     for i in range(2, n):
        if n % i == 0:
            return False
        else:
            return True
   else:
     return False

def highFactor(m):
   factors = []
   for i in range(2, int(math.sqrt(m))):
     if isPrime(i):
        if m % i == 0:
            factors.append(i)
   print max(factors)

highFactor(13195)

所以这显然是在测试他们给出的示例，因为我已经知道答案应该是 29，但是当我运行代码时它给了我 91。我做错了什么？

Answer 1

两个问题:

(1) isPrime 函数在循环的第一次迭代时返回 True。相反，如果您在整个循环中幸存下来而不返回 false，则您希望完成循环，然后返回 True。

(2) 算法可能具有相同质因数的多个副本(即 8 = 2*2*2)。您最好设置 m = m/i 并每次重新启动循环。另外，您可能需要 sqrt(m)+1，因为范围函数不包括上限。