永远需要：Project Euler Problem 3 Python

Question

我是初学者。下面我对欧拉项目3号问题的解决方案需要很长时间才能返回答案。有人能提出改进建议吗？我做错了什么？我写了一些代码来帮助我思考这个问题的所有难题。

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

600851475143的最大质因数是什么？

#limiter identification for iteration

def limiter(x):
    for i in range (2, x):
        if x % i == 0:
            return int (x/i)

#Prime checker 
            
def is_prime(a):
    for i in range (2, a):
        if a % i == 0:
            return False
    return True
#Lists all factors of a given no.

def factorlist(b):
    list = []
    for i in range (2, limiter(b)+1):
        if b % i == 0:
            list.append(i)
    return list

#Lists all prime factors of a given no.

def primefactor(p):
    plist = []
    for i in factorlist(p):
        if is_prime(i)== True:
            plist.append(i)
            
    return plist
    
print (primefactor(600851475143)[-1])

Answer 1

下面是更简单、更短的代码：

# Largest Prime Factor

def prime_number(b):
    c1 = 0
    for i in range(1,int(b/2)+1):
        if b % i == 0:
            c1 += 1
    if c1 < 2:
        return(True)
    else:
        return(False)

def prime_factor(a):
    n = 0
    count = 1
    prime = 0
    while n < a+1:
        n += 1
        if a % n == 0:
            if prime_number(n) == True:
                prime = n
                print(prime)
prime_factor(600851475143)

Answer 2

寻找最大素因子的递归方法将更简单，可能更快：

def lpf(N,p=2):                               # start from preceding prime factor
    for f in range(p,int(N**0.5)+1):          # factors up to square root
        if N%f==0 : return max(f,lpf(N//f,f)) # 1st prime vs lpf of counterpart
    return N # none found, N is prime itself

lpf(600851475143) # 6857

Answer 3

我没有答案，但我要说的是，有时函数中的print（）语句对于在函数中调试很有用。例如，limitor（）函数挂起在71。我发现在我的机器上运行你的程序：

def limiter(x):
for i in range (2, x):
    print(i) <------------------ I added this
    if x % i == 0:
        return int (x/i)

因此，在函数中添加print（）可能会有所帮助。