求素数<n

Question

我在做欧拉计划，第三题。 问题是：

"The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?"

在回答这个问题时，我将任务分解为首先找到所有质数<；x（相反）。为什么下面的代码似乎不起作用，我不确定是逻辑还是运算符的错误使用。在

#A function to find prime numbers under n
def find_prime(n):
    for i in reversed(xrange(2, n)):
        if (n % i) != 0:
            print i

find_prime(n)

在测试中，为了好玩，我还构建了一个质数检查器，所以我做了一些测试。在

^{pr2}$

在我进入下一个解决问题的步骤之前，有谁能帮我理解一下我在find_prime（）函数上的错误之处吗？在

Answer 1

在你开始编码之前，也许你应该先了解一下你正在处理什么。素数研究得很好。首先，你不需要所有的素数，其次，每次你找到一个除数，你就可以把这个数除以这个数，这样就可以得到一个更小的问题。最后，剩下的号码就是你要找的。现在，除了2，没有其他偶数是素数，所以xrange(3, n, 2)。再搜索一些，你会找到一个解决方案，它不需要宇宙的时间来完成。在

Answer 2

你不能判断一个数是否是素数，除非你在整个循环中没有找到任何除数。你报告一个数是质数，只要你找到一个不除它的数，但它可能仍然可以被某个更高的数整除。你的代码会说所有奇数都是素数，因为它们不是2的倍数。在

而且，不必一直到你的范围内的n。一个数的任何因子都不能大于该数的平方根。在

def prime_checker(n):   
  if n > 2:
    for i in range (2, int(n ** .5)+1):
      if (n % i) == 0:
        print "%s is not a prime number" % (n) 
        return false
  print "%s is a prime number" % (n)
  return true