python - 欧拉Q＃3 Python项目

我真的在努力解决欧拉计划问题，以提高自己的数学/编码/问题解决能力，但我对第三个问题有些困惑。问题是“ 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。我做错了什么？

最佳答案

如评论中所述，您的函数过早返回True-例如如果一个数字不能被2整除，这并不意味着它不能被范围（2，n）中的任何后来的数字整除-将51 = 3 * 17作为反示例。

这是您算法的正确版本：

def isPrime(n):
    if n > 1:
        for i in range(2, n):
            if n % i == 0:
                return False
       return True
    else:  # if we have a negative number or 0
       return False

正如其他人提到的那样，有一种更快的方法来检查数字是否为质数。现在，您的函数的复杂度为O(n)，因为您要检查所有不超过n的数字；通过观察n = sqrt(n) * sqrt(n)足以检查直到sqrt(n) + 1

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

关于python - 欧拉Q＃3 Python项目，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37056475/