Project Euler - Problem 3 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) -&gt; 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 &gt; 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 -&gt; returns 29
    print(find_max_prime_factor(13195))
    # 600851475143  prime factors are 6857,1471,839,71 -&gt; returns 6857
    print(find_max_prime_factor(600851475143))
    # 7 is prime therefor -&gt; returns 7
    print(find_max_prime_factor(7))
    # 3452656 prime factors are 2,31,6961 -&gt; returns 6961
    print(find_max_prime_factor(3452656))
    # 896776435 prime factors are 5,17,2549,4139 -&gt; returns 4139
    print(find_max_prime_factor(896776435))


Would love for feedback on my code.Thanks!
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 &gt; 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.