永远需要:Project Euler Problem 3 Python

Question

我是个初学者。我下面针对Project Euler问题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

我没有答案，但我会说，有时函数中的print((语句会被证明对函数中的调试很有用。limiter((函数挂起71的例子。我发现在我的机器上运行你的程序：

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

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

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

这里有一个更简单、更短的代码：

# 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)