эффективные способы нахождения наибольшего простого множителя числа
Я делаю эту проблему на сайте, который я нашел (проект Эйлера), и есть вопрос, который включает в себя поиск наибольшего простого множителя числа. Мое решение терпит неудачу при действительно больших числах, поэтому мне было интересно, как этот код можно упростить?
""" 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)