我正在我发现的网站(项目Euler)上解决此问题，并且有一个问题涉及找到数字中最大的素数。我的解决方案大量失败，所以我想知道如何简化此代码？
""" Find the largest prime of a number """
def get_factors(number):
factors = []
for integer in range(1, number + 1):
if number%integer == 0:
factors.append(integer)
return factors
def test_prime(number):
prime = True
for i in range(1, number + 1):
if i!=1 and i!=2 and i!=number:
if number%i == 0:
prime = False
return prime
def test_for_primes(lst):
primes = []
for i in lst:
if test_prime(i):
primes.append(i)
return primes
################################################### program starts here
def find_largest_prime_factor(i):
factors = get_factors(i)
prime_factors = test_for_primes(factors)
print prime_factors
print find_largest_prime_factor(22)
#this jams my computer
print find_largest_prime_factor(600851475143)
使用大量数字时，它会失败，这是我猜到的问题的重点。 (计算机出现故障，告诉我我的内存不足，并询问我要停止哪些程序)。
************************************** 谢谢您的回答。在任何情况下，代码中实际上都有几个错误。因此，此(无效代码)的固定版本如下。
""" Find the largest prime of a number """
def get_factors(number):
factors = []
for integer in xrange(1, number + 1):
if number%integer == 0:
factors.append(integer)
return factors
def test_prime(number):
prime = True
if number == 1 or number == 2:
return prime
else:
for i in xrange(2, number):
if number%i == 0:
prime = False
return prime
def test_for_primes(lst):
primes = []
for i in lst:
if test_prime(i):
primes.append(i)
return primes
################################################### program starts here
def find_largest_prime_factor(i):
factors = get_factors(i)
print factors
prime_factors = test_for_primes(factors)
return prime_factors
print find_largest_prime_factor(x)
最佳答案
通过您的方法，您首先要在n中生成数字O(n)的所有除数，然后在另一个O(n)调用的test_prime数目(无论如何都是指数)中测试这些除数中的哪一个是质数。
更好的方法是观察到，一旦找到一个数的除数，就可以反复除以该数，以消除所有因素。因此，要获得odt_code的素数，请测试所有小的素数(缓存的)，对于除以数字的每个素数，请保持除法:
830297可被830297整除，因此现在您将使用13进行测试830297 / 13 = 63869仍可被63869整除，您在13上4913不除以13，下一个素数是4913，它将17除以得到4913 289仍然是289的倍数，您拥有17这是除数和终止点。 为了进一步提高速度，在测试了下面表示为
17的缓存素数之后，您必须使用100函数(根据@Ben的答案进行更新)测试素数除数，但从test_prime开始进行相反的操作。您的数字可被sqrt整除，下一个数字将给出71的sqrt，它与最大素数91992有点相似。关于python - 找到大量最大素数的有效方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24166478/