Project Euler #3 Largest prime factor

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.