考虑有限集{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]