List ALL prime-factorized natural numbers in ANY order
Haskell

import Data.List

merge :: [[a]] -&gt; [[a]] -&gt; [[a]]
merge [] ys = ys
merge (x:xs) ys = x : merge ys xs

atmostonefromeach :: [[a]]-&gt; [[a]]
atmostonefromeach = foldr weave undefined

weave :: [a] -&gt; [[a]] -&gt; [[a]]
weave pwrs odds = merge (map (:[]) pwrs) $
foldr (\odd -&gt; merge (odd: (map (:odd) (pwrs)))) undefined odds

primes = nubBy (\x y-&gt;gcd x y &gt; 1) [2..]

shw factors = show (product (map (\(p,k)-&gt;p^k) factors)) ++ ":" ++ concatMap(\(p,k) -&gt; ' ': show p ++ '^': show k) factors

powers p = map (\x-&gt;(p,x)) [1..]

main = mapM_ (putStrLn . shw) $ ([]:) $ atmostonefromeach $ map powers primes


output:

1:
2: 2^1
3: 3^1
4: 2^2
5: 5^1
8: 2^3
6: 2^1 3^1

...


The program constructs,
from the list Q=[q0,q1,..] of composite numbers with all prime factors > p,
the list of those with primes factors >= p, as
merge(P, merge((map(q0*)P1), merge(map(q1*)P1),... 
where P=[p^1,p^2,...] and P1=[p^0,p^1,..].

The name odds in function weave describes the case p==2,
where Q is the set of all odd numbers > 1.