title: Efficiently generate all composite numbers less than N (with their factorizations)
body: <p>I'd like to build an efficient Python iterator/generator that yields:</p>
  
  <ul>
  <li>All composite numbers less than N</li>
  <li>Along with their prime factorization</li>
  </ul>
  
  <p>I'll call it "composites_with_factors()"</p>
  
  <p><em>Assume we already have</em> a list of primes less than N, or a primes generator that can do the same.</p>
  
  <p>Note that I:</p>
  
  <ul>
  <li>DO NOT need the numbers to be yielded in numerical order</li>
  <li>DO NOT care if 1 is yielded at the beginning or not</li>
  <li>DO NOT care if primes are yielded, too </li>
  </ul>
  
  <p>I figure this can be done with a clever recursive generator... </p>
  
  <p>So, for example, a call to composites_with_factors(16) may yield:</p>
  
  <pre><code># yields values in form of "composite_value, (factor_tuple)"
  2, (2)
  4, (2, 2)
  8, (2, 2, 2)
  6, (2, 3)
  12, (2, 2, 3)
  10, (2, 5)
  14, (2, 7)
  3, (3)
  9, (3, 3)
  15, (3, 5)
  5, (5)
  7, (7)
  11, (11)
  13, (13)
  </code></pre>
  
  <p>As you can see from the order of my output, I conceive of this working by starting with the smallest prime on the available primes generator, and outputting all powers of that prime less than N, then try again through the powers of that prime but at each stage seeing if I can apply powers of additional primes (and still be less than N).  When all combinations with THAT prime are done, drop it, and repeat with the next lowest prime number available on the primes generator.</p>
  
  <p>My attempts to do this with "recursive generators" have gotten me very confused on when to pop out of the recursion with "yield ", or "raise StopIteration", or "return", or simply fall out of the recursed function.</p>
  
  <p>Thanks for your wisdom!</p>
  
  <p>ADDITIONAL NOTE:</p>
  
  <p>I <em>do</em> have one way to do this now: I have written a function to factor numbers, so I can factor them down to primes, and yield the results.  No problem.  I keep this blazingly fast by relying on a cache of "what is the lowest prime factor of number N"... for N up to 10 million.</p>
  
  <p>However, once I'm out of the cache, we'll, it devolves to "naive" factoring. (Yuck.)</p>
  
  <p>The point of this post is:</p>
  
  <ul>
  <li>I'm assuming that "generating large composites from their factors" will be faster than "factoring large composites"... especially since I DON'T care about order, and</li>
  <li>How can you have a Python generator "recursively" call itself, and yield a single stream of generated things?</li>
  </ul>