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 express in Python. In C or 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 |
+---------------------+----------+--------------------+---------+