title: Trying to understand a solution to project Euler # 3
body: <blockquote>
    <p>The prime factors of 13195 are 5, 7, 13 and 29.
    What is the largest prime factor of the number 600851475143 ? @ <a href="http://projecteuler.net/problem=3" rel="nofollow">http://projecteuler.net/problem=3</a></p>
  </blockquote>
  
  <p>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 <a href="http://zacharydenton.com/project-euler-solutions/3/" rel="nofollow">Zach Denton's</a> answer and started studying it.  </p>
  
  <p>Here is his code:</p>
  
  <pre><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 &lt;= 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))
  </code></pre>
  
  <p>Here are the bits I can't figure out for myself:</p>
  
  <ol>
  <li>In the second while loop, why does he use a <code>sqrt(n + 1)</code> instead of just <code>sqrt(n)</code>?  </li>
  <li>Why wouldn't you also use <code>sqrt(n + 1)</code> when iterating over the even numbers in the first while loop?  </li>
  <li>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.      </li>
  </ol>