I'm trying to find the largest prime factor of a given number (600851475143) using Python. I've made the following code, but the problem is, it takes forever, probably because it's iterating through lists millions of times. How to optimize this process?
def factors(n):
list = []
i = 1
while i < n:
if n % i == 0:
list.append(i)
i += 1
return list
def prime(n):
list = factors(n)
primelist = []
for item in list[1:]:
if item % 2 != 0 and item % 3 != 0 and item % 4 != 0 and item \
% 5 != 0 and item % 6 != 0 and item % 7 != 0 and item % 8 != 0 \
and item % 9 != 0:
primelist.append(item)
return primelist
def greatestprime(n):
list = prime(n)
list[0] = lnum
i = 1
while i < len(list):
if list[i] > lnum:
lnum = list[i]
return lnum
#print(greatestprime(600851475143))