项目欧拉问题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

如注释中所述，您的函数过早返回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

Answer 2

正如奥斯汀所评论的isPrime过早地返回true。通过将return True移出for循环，函数将检查range(2, n)中的每个数字，然后确认该数字是素数。你知道吗

假设你要做isPrime(13)，它应该返回True

在for循环的第一个过程中if n % i == 0将是if 13 % 2 == 0，这是错误的。由于for循环中的else: return True，函数将返回True并终止。你知道吗

要解决这个问题，您可以编写isPrime()，如：

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

Answer 3

两个问题：

（1）isPrime函数在循环的第一次迭代中返回True。相反，您希望完成循环，然后返回True，前提是您在整个循环中都没有返回false。你知道吗

（2）一个算法有可能有相同素数因子的多个副本（即8=2*2*2）。最好设置m=m/i，每次都重新启动循环。另外，您可能需要sqrt（m）+1，因为range函数不包括上限。你知道吗