3

我正在尝试在 Python 中解决 Project Euler 问题 3：

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

我知道我的程序效率低下且过大，但我只是想知道为什么它不起作用？这是代码：

def check(z):

# checks if the given integer is prime

    for i in range(2, z):
        if z % i == 0:
            return False
            break
        i = i+1
    return True

def primegen(y):
# generates a list of prime integers in the given range

    tab = []
    while y >= 2:
        if check(y) == True:
            tab.append(y)
        i = i-1


def mainfuntion(x):
# main function; prints the largest prime factor of the given integer

    primegen(x)
    for i in range(len(tab)):
        if x % tab[i] == 0:
            print tab[i]
            break

mainfuntion(600851475143)

这是错误：

for i in range(2, z):
OverflowError: range() result has too many items
4

4 回答 4

11

原因是 Python 中的列表限制为 536,870,912 个元素（请参阅Python 数组可以获取多大？），当您在示例中创建范围时，元素的数量超过了该数量，从而导致错误。

Project Euler 的乐趣在于您自己解决问题（我知道您正在这样做:)），所以我将给出一个非常小的提示来绕过该错误。想想一个数的因数是什么——你知道 600851475142 不可能是 600851475143 的因数。因此你不必一直检查到那个数。按照这个逻辑，有没有办法可以显着减少检查的范围？如果您对素数的性质进行一些研究，您可能会发现一些有趣的东西:)

于 2012-11-21T22:56:04.580 回答
1

这是我使用的代码！！

n = 600851475143
i = 2
while i * i < n:
     while n % i == 0:
         n = n / i
     i = i + 1

print n

-M1K3

于 2013-03-02T02:59:46.897 回答
1

首先，在第一个代码块中，不要使用，i = i+1因为 for 循环会处理它。其次，用于xrange制作生成器而不是列表。

于 2012-11-21T23:07:14.830 回答
1

@seamonkey8：您的代码可以改进。您可以将其增加 2 而不是 1。对于非常高的数字，它会产生速度差异：

n,i = 6008514751231312143,2

while i*i <= n:      
    if n%i == 0:
        n //= i
    else: 
        i+=[1,2][i>2]
于 2014-12-13T16:47:51.303 回答