# 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.

Solution

``````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]
[2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28]
``````

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]
[100,105,108,112,120,125,126,128,135,140]
``````