title: What makes this prime factorization so efficient?
body: <p>I've been doing some Project Euler problems to learn/practice Lua, and my initial quick-and-dirty way of finding the largest prime factor of <code>n</code>was pretty bad, so I looked up some code to see how others were doing it (in attempts to understand different factoring methodologies).</p>
  
  <p>I ran across the following (originally in Python - this is my Lua):</p>
  
  <pre><code>function Main()
      local n = 102
      local i = 2
      while i^2 &lt; n do
          while n%i==0 do n = n / i end
          i = i+1
      end
      print(n)
  end
  </code></pre>
  
  <p>This factored huge numbers in a <strong>very</strong> short time - almost immediately. The thing I noticed about the algorithm that I wouldn't have divined:</p>
  
  <ul>
  <li><code>n = n / i</code></li>
  </ul>
  
  <p>This seems to be in all of the decent algorithms. I've worked it out on paper with smaller numbers and I can see that it makes the numbers converge, but I don't understand why this operation converges on the largest prime factor.</p>
  
  <p>Can anyone explain?</p>