Euler Project #3 in Python

Question

我正在尝试解决Python中的欧拉项目问题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

Answer 1

原因是 Python

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

欧拉项目的乐趣在于自己弄清楚这些东西（我知道你正在做:)），所以我会给出一个非常小的提示来绕过这个错误。想想数字的因子是什么——你知道600851475142不可能成为600851475143的因素。因此，您不必一直检查到该数字。按照这个逻辑，有没有办法显着减少你检查的范围？如果你对素因数的性质做一些研究，你可能会发现一些有趣的东西:)

Answer 2

这是我使用的代码！！

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

-M1K3

Answer 3

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

n,i = 6008514751231312143,2
while i*i <= n:      
    if n%i == 0:
        n //= i
    else: 
        i+=[1,2][i>2]