algorithm to find products of a set of primes, in order, greater than x

Consider the finite set {2,3,5,...,n}. I am interested in primes but the question could apply to any set of numbers. I want to find all possible products of these numbers in ascending order, and in particular greater than or equal to some number x. Does anyone know a nice algorithm for this?

EDIT to clarify:

Each factor in the input set may be used any number of times. If the input were {2,3,5,7} the output would be {2,3,4,5,6,7,8,9,10,12,14,15,16,18,...}. The algorithm can stop as soon as it produces a result greater than or equal to some number x.


  • A Haskell code, as seen in this answer,

    hamm :: [Integer] -> [Integer]
    hamm []     = []   
    hamm (p:ps) = xs        -- e.g. hamm [2,3,5] 
            where xs = merge (hamm ps)               --   H({p} ∪ ps) = S,
                             (p : map (p*) xs)       -- S ⊇ {p} ∪ H(ps) ∪ { p*x | x ∊ S }
    merge a@(x:xs) b@(y:ys) | x < y     = x : merge xs b 
                            | otherwise = y : merge a ys 
    merge [] b = b
    merge a [] = a

    merge here doesn't try to eliminate multiples, because there won't be any -- but only in case you're using only the primes in the input:

    ~> take 20 $ hamm [2,3,5,7]

    If not, you need to use union instead,

    union a@(x:xs) b@(y:ys) | x < y     = x : union xs  b
                            | x > y     = y : union a  ys
                            | otherwise = x : union xs ys
    union [] b = b
    union a [] = a

    Starting from (above) a given value efficiently might be an interesting challenge. A directly slice-generating code at the bottom of this answer could be taken as a starting point.

    In general it is easy to skip along the ordered sequence until a value is passed over. In Haskell, it is done with a built-in dropWhile (< n),

    ~> take 10 $ dropWhile (< 100) $ hamm [2,3,5,7]