欧莱士问题№3，大数字上的代码结构

Question

我目前正在学习Python，并与euler的问题一起练习。我被困在第三个问题上，我的代码不适用于较大的数字，但与其他数字的代码是工作的。

n = 600851475143 
x = 0
for i in range(2,n):
    if(n%i == 0):
        if(x < i): x = i
print(x)

控制台没有得到任何结果和垃圾。P.S https://projecteuler.net/problem=3

(对不起，我的英语很差)

Answer 1

它在运行，但它所需的时间是巨大的。您可以检查下面的代码，它将继续打印x的代码。

n = 600851475143
x = 0
for i in range(2, n):
    if n % i == 0:
        if x < i:
            x = i
            print(x)

为了节省时间，您可以尝试以下代码而不是代码：

n = 600851475143
x = 0
for i in range(2, n):
    if n % i == 0:
        x = n // i
        break
print(x) 

立即打印8462696833。但正如@seesharper在评论中指出的那样，它只是最大的因素，而不是主要因素。因此，这不是项目Euler问题#3的正确答案。

Answer 2

from tqdm.auto import tqdm

n = 600851475143 
x = 0
for i in tqdm(range(2,n)):
    if(n%i == 0):
        x = i
print(x)

如果使用经典python，您的程序将至少持续40分钟，这就是您没有输出的原因。我建议您要么使用numpy来通过，要么添加一个步骤，因为我认为即使是数字也不起作用。

我使用tqdm来估计for循环运行所需的时间，您可以使用pip install tqdm下载它。

Answer 3

检查这段代码可以节省很多时间。

利用sqrt进行优化

from math import sqrt
def Euler3(n):
    x=int(sqrt(n))
    for i in range(2,x+1):
        while n % i == 0:
            n //= i
            if n == 1 or n == i:
                return i
    return n
n = int(input())
print(Euler3(n))

另外，检查我的欧拉吉特回购

在python2中只有6种解决方案，而且它非常古老，但它们都经过了很好的优化。