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

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

StackExchange Code Review Q#104997, answer score: 7