You could operate over a list of all prime factors less than N to produce an unordered, but complete list of numbers less than N.
- Generate a list of all prime numbers with up to N. So, you got p1, p2, ..., pn.
- Make a list of matching exponents for every prime number. So, now you have a data structure representing p1e1, p2e2, ..., pnen
Now, to the fun part:
- Initialize all exponents with zero. This gives you the prime factorization of 1.
- Now, start with the first prime number, and increment its exponent. You got another new number, multiply the prime factors, save it for later.
- Is the number bigger than N? Trash the number. Set the exponent back to 0. Increment the exponent of the next bigger prime. Is that too big as well? Set the exponent to 0 too, increment the next prime exponent. Repeat until you produce a number < N.
- Repeat at step 2.
If you cannot increment any exponent in step 3 any more, you have produced every natural number, alongside with their prime factorization.
For example, producing every number <= 6:
- The prime numbers would be 2,3,5
- Start with exponents being 0,0,0:
- 20 * 30 * 50 = 1 -> save it.
- Increment the exponent of the lowest prime factor:
- 21 * 30 * 50 = 2 -> save it
- Increment the exponent of the lowest prime factor:
- 22 * 30 * 50 = 4 -> save it, notice we are missing 3, but we'll get there
- Increment the exponent of the lowest prime factor:
- 23 * 30 * 50 = 8 -> Trash it, 8 > 6
- Set exponent of the lowest prime factor back to zero, increment the next exponent
- 20 * 31 * 50 = 3 -> save it.
- Increment the exponent of the lowest prime factor:
- 21 * 31 * 50 = 6 -> save it.
- Increment the exponent of the lowest prime factor:
- 22 * 31 * 50 = 12 -> Trash it, 12 > 6
- Set exponent of the lowest prime factor back to zero, increment the next exponent
- 20 * 32 * 50 = 9 -> Trash it, 9 > 6
- Set exponent of the next to lowest prime factor back to zero, increment the next exponent
- 20 * 30 * 51 = 5 -> Save it.
- Since your list of results now has 6 elements, you are finished.