Project Euler - Problem 3

Question

The description of the problem is:

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

Here is my solution:

import heapq
from math import sqrt


def find_max_prime_factor(n: int) -> int:
    '''
    returns the largest prime factor of the non negative integer n
    :param n: the number we want to find the max prime factor of
    :return: the largest prime factor of n
    '''
    max_heap = []
    # Checking for 2 as prime factor
    if n % 2 == 0:
        heapq.heappush(max_heap, -2)
        # dividing by 2 until n becomes odd
        while n % 2 == 0:
            n = n/2
    # dealing with odd numbers
    for i in range(3,int(sqrt(n)),2):
        if n % i == 0:
            heapq.heappush(max_heap,-1*i)
            while n % i == 0:
                n = n/i

    # dealing with case where n is a prime by itself
    if n > 2:
        return n

    return heapq.heappop(max_heap) * (-1)

Here's some examples and test-cases:

from ProjectEuler.problem3 import find_max_prime_factor

if __name__ == "__main__":
    # 13195 prime factors are 5,7,13,29 -> returns 29
    print(find_max_prime_factor(13195))
    # 600851475143  prime factors are 6857,1471,839,71 -> returns 6857
    print(find_max_prime_factor(600851475143))
    # 7 is prime therefor -> returns 7
    print(find_max_prime_factor(7))
    # 3452656 prime factors are 2,31,6961 -> returns 6961
    print(find_max_prime_factor(3452656))
    # 896776435 prime factors are 5,17,2549,4139 -> returns 4139
    print(find_max_prime_factor(896776435))

Would love for feedback on my code.Thanks!

Answer 1

    max_heap = []

I think the essentially Hungarian naming here is actually fairly helpful, but it would be very useful to have a comment explaining that the library support is only for min heaps, so everything must be negated when pushed or popped.

---

    # Checking for 2 as prime factor
    if n % 2 == 0:
        heapq.heappush(max_heap, -2)
        # dividing by 2 until n becomes odd
        while n % 2 == 0:
            n = n/2
    # dealing with odd numbers
    for i in range(3,int(sqrt(n)),2):
        if n % i == 0:
            heapq.heappush(max_heap,-1*i)
            while n % i == 0:
                n = n/i

Reasonable use of a special case: I see you've given some thought to optimisation.

It's better to use -i than -1*i, and n // i (since you want integer division) than n / i.

---

    # dealing with case where n is a prime by itself

That's open to misinterpretation. Is it talking about the original value of n or the current value? I think I would phrase it

    # if n > 1 here then it's a prime

---

    return heapq.heappop(max_heap) * (-1)

See previous point about unary minus.

---

I wanted to address minor improvements before addressing the big one. Why use a heap at all? The largest prime is the last prime encountered, and there's no need to store the smaller ones. Removing the heap would make the code simpler and faster.

Answer 2

As you will quickly realize, a lot of Project Euler problems involve prime numbers. It is therefore a good idea to write a good prime generating function early on. I usually use a simple Sieve of Eratosthenes. With that function it is easy to write a function that gets the prime factorization of a number (something you will also need again). After you got that, just use the built-in max.

from math import sqrt
from itertools import takewhile

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, primes=None):
    limit = int(sqrt(n)) + 1
    if primes is None:
        primes = prime_sieve(limit)
    else:
        primes = takewhile(lambda p: p < limit, primes)
    for p in primes:
        while n % p == 0:
            yield p
            n //= p
    if n > 1:  # n is prime
        yield n

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