4
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The worst case running time is O(sqrt n) which happens when n is prime. \$\endgroup\$
    – ErikR
    Sep 18, 2015 at 6:34
  • \$\begingroup\$ Can you please give some detail? \$\endgroup\$
    – CodeYogi
    Sep 18, 2015 at 7:24

3 Answers 3

7
\$\begingroup\$

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 |
+---------------------+----------+--------------------+---------+
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – CodeYogi
    Sep 18, 2015 at 11:20
2
\$\begingroup\$
  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.

\$\endgroup\$
1
  • \$\begingroup\$ Done here! but I think it can be made a lot cleaner. \$\endgroup\$
    – CodeYogi
    Sep 18, 2015 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.