Trying to understand a solution to project Euler # 3
Question: > The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime
> factor of the number 600851475143 ? @ <http://projecteuler.net/problem=3>

I have a deal going with myself that if I can't solve a project Euler problem
I will understand the best solution I can find. I did write an algorithm which
worked for smaller numbers but was too inefficient to work for bigger ones. So
I googled [Zach Denton's](http://zacharydenton.com/project-euler-solutions/3/)
answer and started studying it.

Here is his code:

    
    
    #!/usr/bin/env python
    import math
    
    def factorize(n):
        res = []
        # iterate over all even numbers first.
        while n % 2 == 0:
            res.append(2)
            n //= 2
        # try odd numbers up to sqrt(n)
        limit = math.sqrt(n+1)
        i = 3
        while i <= limit:
            if n % i == 0:
                res.append(i)
                n //= i
                limit = math.sqrt(n+i)
            else:
                i += 2
        if n != 1:
            res.append(n)
        return res
    
    print max(factorize(600851475143))
    

Here are the bits I can't figure out for myself:

  1. In the second while loop, why does he use a `sqrt(n + 1)` instead of just `sqrt(n)`? 
  2. Why wouldn't you also use `sqrt(n + 1)` when iterating over the even numbers in the first while loop? 
  3. How does the algorithm manage to find only prime factors? In the algorithm I first wrote I had a separate test for checking whether a factor was prime, but he doesn't bother. 


Answer:   1. I suspect the `+1` has to do with the imprecision of `float` (I am not sure whether it's actually required, or is simply a defensive move on the author's part).

  2. The first `while` loop factors all twos out of `n`. I don't see how `sqrt(n + 1)` would fit in there.

  3. If you work from small factor to large factors, you automatically eliminate all composite candidates. Think about it: once you've factored out `5`, you've automatically factored out `10`, `15`, `20` etc. No need to check whether they're prime or not: by that point `n` will not be divisible by them.

I suspect that checking for primality is what's killing your original
algorithm's performance.

