考虑有限集{2,3,5,…,n}。我对素数感兴趣,但这个问题可以应用于任何一组数字。我想找到这些数字的所有可能乘积,以升序排列,特别是大于或等于某个数字x。有人知道一个很好的算法吗?
编辑以澄清:
输入集中的每个因子可以使用任意次数。如果输入为{2,3,5,7},则输出为{2,3,4,5,6,7,8,9,10,12,14,15,16,18,…}一旦产生大于或等于某个数字x的结果,算法就可以停止。

最佳答案

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]

10-06 10:19
查看更多