# 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) -> 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!

    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.

• At first I thought about returning the whole prime factorization array, maybe for further utilization if needed, and thought that the max_heap would solve me both problems. in the context of this specific question you are totally right. thanks! :) Commented Jul 31, 2019 at 14:21
• By the way, why is -i better than using -1*i? I couldn't find it by googling. Commented Jul 31, 2019 at 14:25
• It's easier to read, and (depending on compiler and architecture) may be faster. Commented Jul 31, 2019 at 14:29

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