按顺序查找一组大于 x 的素数的乘积的算法

Question

考虑有限集 {2,3,5,...,n}。我对质数很感兴趣，但这个问题可以适用于任何一组数字。我想按升序查找这些数字的所有可能乘积，尤其是大于或等于某个数字 x 的乘积。有人知道一个很好的算法吗？

编辑澄清:

输入集中的每个因素都可以使用任意次数。如果输入是 {2,3,5,7} 输出将是 {2,3,4,5,6,7,8,9,10,12,14,15,16,18,...} .一旦产生大于或等于某个数字 x 的结果，算法就会停止。

Answer 1

Haskell 代码，如 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这里不会尝试消除倍数，因为不会有任何 - 但前提是您在输入中使用仅素数:

~> 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]

如果没有，你需要使用union相反，

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

有效地从(以上)给定值开始可能是一个有趣的挑战。 this answer底部直接切片生成代码可以作为起点。

通常很容易沿着有序序列跳过，直到传递一个值。在 Haskell 中，它是通过内置的 dropWhile (< n) 完成的。 ,

~> take 10 $ dropWhile (< 100) $ hamm [2,3,5,7]
[100,105,108,112,120,125,126,128,135,140]