title: Iterating over numbers including prime factors
body: <p>I want to iterate over all numbers from 1 to n, and I need to know the primes factors of each number. A simple implementation would be to simply iterate over all numbers from 1 to n and calculate the prime factors of each, taking a time of O(n^(3/2)).</p>
  <p>I've come up with this solution which generates each number exactly once, and one number (which is not yielded) extra per prime number, having a time complexity of O(n + p).</p>
  <pre class="lang-py prettyprint-override"><code># primes contains enough primes so accessing it will never fail.
  # Generate numbers 1 to limit (inclusive) including prime factors.
  def gen(limit, i=0):
      # Primes above the limit are used 0 times, p**0 = 1
      if primes[i] &gt; limit:
          yield 1, {}
          return
  
      # Generate all numbers using only higher primes...
      for n, f in gen(limit, i + 1):
          # ...and then add the current prime as often as possible each time.
          while n &lt;= limit:
              yield n, f.copy()
  
              n *= primes[i]
              cf = f.get(primes[i], 0)
              f[primes[i]] = cf + 1
  </code></pre>
  <p>This prints the correct result for small limits. However, this solution is recursive, and reaches the maximum stack size quite fast. The output is as</p>
  <pre><code>1 {}
  2 {2: 1}
  4 {2: 2}
  8 {2: 3}
  3 {3: 1}
  6 {3: 1, 2: 1}
  9 {3: 2}
  5 {5: 1}
  10 {5: 1, 2: 1}
  7 {7: 1}
  </code></pre>
  <p>Note that I don't expect the numbers to be generated in-order.</p>
  <p>Is it possible to transform this into an iterative solution, or is there a simpler one entirely?</p>