Euler problem 3: largest prime factor of the number I have been trying to learn Python and just solved Euler Problem 3:


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


I am looking for any feedback on improving efficiency and the code itself.

My code:

from itertools import count, islice

def is_prime(number):
    for n in islice(count(2), int(number**0.5 -1)):
        if number % n == 0:
            return False
    return True


def find_factors(number):
    lst = []
    for n in islice(count(2), int(number/2-1)):
        if number % n == 0:
            if is_prime(n):
                lst.append(n)
    return lst


print(find_factors(13195).pop())


I used islice instead of xrange because of int limits, which I learned about from another question at StackOverflow.com

In code above, I have created two separate functions, one to find a prime and the other to find factors.

The program works this way,


It takes an input number
Find all the factors of that number from 2-&gt;number/2
If it finds a factor, it checks if its a prime, and append it to a list.
Eventually I print the last element of list since list in python are ordered.
When I look at your solution, the first impression I get is that it's too complicated. To solve the problem you don't need any fancy algorithms for prime numbers, or islice and count. It's a simple task of trying to divide by possible factors. 

One important thing to note is that we only need to check for prime factors that are smaller than the square root of the number. Once we have reached the square root, there can be only one remaining factor, which can be proved by contradiction. 

Another important thing to note is that once we have found a prime factor, we can divide the original number by that factor and reduce our problem size.

Doing both of these things, I end up with something like this: 

def get_max_prime_factor(n):
    d = 2
    factors = []
    while d*d &lt;= n:
        while n%d == 0:
            n //= d
            factors.append(d)
        d += 1
    if n != 1:
        factors.append(n)
    return max(factors)


Now, I'll say that even this implementation might be too complicated, since I'm saving all prime factors in a list instead of only keeping track of the largest one. If you want you could change that implementation and make it even more efficient, but to solve the problem above it's not necessary.