Euler problem 3: largest prime factor of the number

Question

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->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.

Answer 1

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 <= 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.

Answer 2

Another, slightly slower, approach, but which helps you in future Project Euler problems, is using the same algorithm as in the answer by @maxb, but instead of dividing by every number, only divide by the primes up to \$\sqrt{n}\$. For this you can use a prime sieve (a fast method to get all primes up to some number):

def prime_sieve(limit):
    prime = [True] * limit
    prime[0] = prime[1] = False

    for i, is_prime in enumerate(prime):
        if is_prime:
            yield i
            for n in range(i * i, limit, i):
                prime[n] = False

def prime_factors(n):
    for p in prime_sieve(int(n ** 0.5) + 1):
        while n % p == 0:
            n //= p
            yield p
    if n != 1:
        yield n

if __name__ == "__main__":
    for n in (13195, 600851475143):
        print(n, max(prime_factors(n)))

Here I used a basic implementation of the sieve of Eratosthenes in pure Python. Faster implementations exist.

Some speed comparisons:

%timeit max(prime_factors(13195))
19.2 µs ± 771 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit get_max_prime_factor(13195)
3.55 µs ± 68.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit find_factors(13195).pop()
873 µs ± 217 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

And for the actual number in the problem:

%timeit max(prime_factors(600851475143))
120 ms ± 1.54 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit get_max_prime_factor(600851475143)
394 µs ± 6.68 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit find_factors(600851475143).pop()
running for more than 10 minutes...