Return to Revisions

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

Using itertools.count:

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