在Python中找到最大的素数因子太慢了(Finding largest prime factor too slow in Python)

在Python中找到最大的素数因子太慢了(Finding largest prime factor too slow in Python)

题：

13195的主要因素是5,7,13和29. 600851475143的最大主要因素是什么？

我尝试使用下面的代码解决它，它需要很长时间才能运行。 有没有最好的方法来解决这个问题？

def find_prime(num, ranger): count = 0 prime = True for i in range(2, num): if num % i == 0: count = count + 1 if count > 1: prime = False return prime return prime prime_list = [] target = 600851475143 for i in range(2,target ): if target % i == 0: print(i) if find_prime(i,target) and i % 2 == 0: prime_list.append(i) print(prime_list) print(max(prime_list))

请建议。

Question:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

And I tried to solve it by using the below snippet, its taking long time to run. Is there any best way to solve this problem?

def find_prime(num, ranger): count = 0 prime = True for i in range(2, num): if num % i == 0: count = count + 1 if count > 1: prime = False return prime return prime prime_list = [] target = 600851475143 for i in range(2,target ): if target % i == 0: print(i) if find_prime(i,target) and i % 2 == 0: prime_list.append(i) print(prime_list) print(max(prime_list))

Please suggest.

最满意答案

n=600851475143 d=2 while d < n/d: if n%d==0: n/=d else: d+=1 print n n=600851475143 d=2 while d < n/d: if n%d==0: n/=d else: d+=1 print n