11

我刚刚开始学习用 Python 编码。我正在尝试编写一些代码来回答这个 Project Euler 问题：

13195 的质因数是 5、7、13 和 29。

数字 600851475143 的最大质因数是多少？

我的程序适用于 13195 的测试用例，但是当我尝试输入 600851475143 时，出现错误：“OverflowError: range() results has too many items” 有谁知道我该如何解决这个问题？

这是我的代码：

class Euler3:
    "A class to find the largest prime factor of a given number"
     n = 600851475143
     primeFactors = []
     for i in range(2,n):
         if (n%i ==0):
            primeFactors.append(i)
            n = n/i
            i = i -1 #reset i
     print primeFactors

任何帮助或建议将不胜感激！

4

8 回答 8

18

该range函数创建一个列表并尝试将其存储在内存中。创建一个长很多数字的列表是导致溢出错误的原因。您可以xrange改为使用生成器来按需生成数字。

也就是说，我想你会发现你的算法对于计算大素数来说太慢了。有很多素数算法，但我可能建议您以埃拉托色尼筛法为起点。

编辑：正确地xrange实际上并没有返回一个生成器，而是一个 xrange 对象，它的行为很像一个生成器。我不确定你是否在乎，但我不准确让我很烦恼！

于 2012-05-28T02:40:45.667 回答
4

我猜你使用的是 python 2 而不是 python 3——range(2,n)实际上是在构造一个列表！你没有足够的内存来存储 6000 亿个数字！xrange不过应该没问题。

另外，你的想法是i=i-1行不通的。For 循环不像 C 那样工作，而且这种 hack 只适用于 C 风格的循环。for 循环遍历range(2,n). 如果在一次迭代中i获取该值5，那么无论您对 做什么i，它仍然会6在下一次通过。

此外，range(2,n)当您进入循环时，将构建列表。因此，当您修改 时n，这不会改变任何内容。

你将不得不重新考虑你的逻辑。

（如果你不相信我，尝试使用 175 作为测试用例）

作为最后的评论，您可能应该养成使用特殊整数除法的习惯：n = n // i. 虽然/和//在 python 2 中的工作方式相同，但这确实是不推荐使用的行为，并且它们在 python 3 中的工作方式不同，它/会给你一个浮点数。

于 2012-05-28T02:38:56.990 回答
4

您可以通过使用xrange而不是解决问题range

您的下一个问题将是程序运行时间过长，因为您需要在某些情况下跳出循环

处理重复因素的更好方法是if将while

     while (n%i ==0):
        primeFactors.append(i)
        n = n/i
于 2012-05-28T02:38:58.207 回答
2 
n = 600851475143
primeFactors = []
for i in range(2,n):

我认为您可以通过注意到这一点来优化功能

for i in range(2,n):

你可以更换

range(2,n)

经过

range(2,int(sqrt(n))+2)

因为，你可以看到维基...

于 2012-05-28T02:56:17.563 回答
1

我花了大约 5 秒钟才得到答案。

import math

def is_prime_number(x):
   for i in range(int(math.sqrt(x)), 2, -1):
      if x % i == 0:
        return False
   return True

def next_prime_number(number):
    #Returns the next prime number.
    if number % 2 == 0 and number != 2:
        number += 1
    while not is_prime_number(number):
        number += 2
    return number

num = 600851475143
i = 2
while (i < long(math.sqrt(num) / 2)):
    if num % i == 0:
       largest = i
       print largest
    i = next_prime_number(i + 1)
于 2014-04-13T11:25:19.017 回答
1

这是找到迄今为止我发现的素数的最佳方法：

def isprime(n):
    #make sure n is a positive integer
    n = abs(int(n))
    #0 and 1 are not primes
    if n < 2:
        return False
    #2 is the only even prime number
    if n == 2:
        return True
    #all other even numbers are not primes
    if not n & 1:
        return False
    #range starts with 3 and only needs to go up to the square root of n
    #for all odd numbers
    for x in range (3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True #if it makes it through all the catches, it is a prime
于 2014-01-15T08:49:50.633 回答
1

xrange 可能不会帮助你（或者它可能！），但这里的关键是要意识到你不需要找到直到 600851475143 或 600851475143 的因数的素数，但它是素数，所以.. . 使用良好的旧素数分解方法，如下所示：

A=600851475143
n=2
fac=[]
while(n<=int(A)):
    B=1
    while(A%n==0):
        B=0   
        A=A/n
    if(B==0):
        fac.append(n)
    n=n+1

print max(fac)

这将几乎立即返回最大的素数

于 2014-10-05T08:26:32.980 回答
0

我也在与这个 Python “OverflowError”作斗争，在这个项目上工作。想出一个有效的组合让我发疯了。

但是，我确实发现了一种聪明的方法，至少我是这么认为的:)。

这是我解决这个问题的代码。

def IsNumberPrime(n):
   bounds = int(math.sqrt(n))
   for number in xrange(2,bounds+2):
        if n % number == 0:
            return False
   return True

def GetListOfPrimeFactors(n):
    primes = []
    factors = GetListOfFactors(n)
    if n % 2 == 0:
       primes.append(2)

    for entries in factors:
       if IsNumberPrime(entries):
          primes.append(entries)
    return primes


GetListOfPrimeFactors(600851475143)

def GetListOfFactors(n):
   factors = []
   bounds = int(math.sqrt(n))
   startNo = 2

   while startNo <= bounds:
      if n % startNo == 0:
         factors.append(startNo)
      startNo += 1
   return factors

我所做的是将输入的数字的因素输入到“因素”列表中。之后，我获取因子列表并确定哪些是素数并将它们存储到一个列表中，然后打印出来。

我希望这有帮助

——迈克

于 2013-06-07T10:19:02.987 回答