# Project Euler #3 Largest prime factor

Given

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

def max_factor(num):
"""Find the maximum prime factor."""
factor = 2
while factor * factor <= num:
while num % factor == 0:
num /= factor
factor += 1
if (num > 1):
return num
return factor

print max_factor(33) #11
print max_factor(38) #19
print max_factor(600851475143) #6857


This problem is already discussed a lot. I am more interested in finding the running time complexity. Since input here is just a number how to relate the running time to the input size. Also, I sense that running time should be logarithmic but how to derive that exactly seems quite tough.

• The worst case running time is O(sqrt n) which happens when n is prime. – ErikR Sep 18 '15 at 6:34
• Can you please give some detail? – CodeYogi Sep 18 '15 at 7:24

Also, I sense that running time should be logarithmic but how to derive that exactly seems quite tough.

Nope, running time is $O(\sqrt N)$ worst-case. Consider the case of a prime number (or particularly bad cases, like the product of twin primes). You have to check $\sqrt N$ possible values to find the answer. No way around that.

Code-wise, you have a bug, only minor/trivial comments otherwise. First the bug. The issue is here:

return factor


What is factor at the end? It's just the first number whose square is larger than whatever num has become. It's not necessarily a factor of the original value. It's just an index. As an example, max_factor(8) == 3, max_factor(9) == 4, etc. You need to keep track of which of the attempted factors actually are factors. Something like:

def max_factor(num):
"""Find the maximum prime factor."""
best = None
factor = 2
while factor * factor <= num:
while num % factor == 0:
best = factor
num /= factor
factor += 1
if (num > 1):
return num
return best


As others have pointed out, you don't do input validation. I don't really consider that hugely important here and it's perfectly fine to just require that the user passes reasonable numbers in. But it couldn't hurt to just make that explicit:

def max_factor(num):
"""Find the maximum prime factor."""
assert num >= 2
...


Otherwise, you have a counting loop with a non-trivial condition. This is one of those things that's always annoying to expression in Python. In C/C++, that'd be:

for (factor=2; factor*factor <= num; ++factor) { ... }


and we have everything on one line. In Python, we have three options, none of which I'm thrilled about. Yours:

factor = 2
while factor * factor <= num:
...
factor += 1

for factor in itertools.count(start=2):
if factor * factor > num: break
...


Using itertools.takewhile and count():

for factor in itertools.takewhile(lambda f: f*f <= num, itertools.count(start=2)):
...


Yeah, even if we put everything on one line, I'm not sure that helps any. Meh.

Lastly, factor-checking. The factors you are checking, in order, are:

2, 3, 4, 5, 6, 7, 8, ...


That is pretty inefficient. First, once you check 2, you don't need to check any of the even numbers. Similarly for 3 and multiples of 3. A more efficient check would be:

2, 3 then 5, 7, 11, 13, 17, 19, 23, ...


Basically alternating adding 2 and 4 from then on out. We end up with just odd numbers that aren't multiples of 3. So we only have to check 2 numbers out of every 6. We could write a generator for that:

def potential_factors(num):
yield 2
yield 3

fact = 5
incr = 2
while fact * fact <= num:
yield fact
fact += incr
incr ^= 6


Which we can use:

def max_factor_mine(num):
assert num >= 2

def potential_factors():
yield 2
yield 3

fact = 5
incr = 2
while fact * fact <= num:
yield fact
fact += incr
incr ^= 6

best = None
for factor in potential_factors():
while num % factor == 0:
best = factor
num /= factor

return num if num > 1 else best


That's about as good as you're going to get with this approach. If you want better performance, you'd have to get a different algorithm. In this answer, I show an approach with Pollard's rho, which would give a dramatic performance improvement just by doing something completely different:

+---------------------+----------+--------------------+---------+
|                     | OP       | OP w/fewer factors | Pollard |
+---------------------+----------+--------------------+---------+
| 600851475143        |  0.003s  |  0.002s            |  0.092s |
| 145721 * 145723     |  0.298s  |  0.174s            |  0.018s |
| 1117811 * 1117813   |  2.286s  |  1.331s            |  0.262s |
| 18363797 * 18363799 | 40.379s  | 21.895s            |  0.825s |
+---------------------+----------+--------------------+---------+


You don't perform any parameter validation, so look what happens when I do these:

>>> f(1)
2
>>> f(0)
2
>>> f(-12312321)
2


The simple way to avoid this is

def max_factor(num):
if num < 2:
raise ValueError("Only numbers greater than 1 are allowed.")


Alternatively you could handle each case if they're acceptable inputs to the algorithm (I'm not sure of the maths here). 0 and 1 are easy since they're their own factors if they're considered valid:

if num in (1, 0):
return num


For negative numbers, you need num to be positive so that your algorithm works. You can turn it positive using abs. Before that you can just set a boolean that checks for a negative parameter then at the end you can check this value to see whether or not to return a negative number.

negative = num < 0
num = abs(num)

...

if (num > 1):
return num if not negative else -num
return factor if not negative else -factor


Whatever you decide is valid input should be noted in the docstring so that people don't have to just try passing parameters to see what's permissable.

def max_factor(num):
"""Find the maximum prime factor for num > 1."""


I also think that this is a complicated algorithm for someone not already familiar with it. I had to read the wikipedia page on max prime factor to realise how this works. A couple comments on the method behind it may be hard to manage, but referencing that it's a known algorithm for people to look up would at least clue them in that it's Googleable and not something you invented.

• Ya I agree, I am having hard time doing project Euler. But I want to improve my programming and logic abilities. Please let me know if you know the path to follow. – CodeYogi Sep 18 '15 at 11:20
1. You should always ask what the corner cases are. What would you expect max_factor(1) to return?

2. Your code is buggy. You have return fact but fact isn't assigned anywhere. If you changed it to return factor as suggested in comments, it would still be buggy: max_factor(8) would return 3.

• Done here! but I think it can be made a lot cleaner. – CodeYogi Sep 18 '15 at 11:49