1

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

编辑澄清：

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

4

7 回答 7

3

（编辑：让它按升序生产所有产品；让用户根据需要过滤它们。这是一个广义的汉明数问题）

genHamming     :: Integral a => [a] -> [a]
genHamming  zs = hmng where
         hmng = 1 : foldr (||) []  [map (z*) hmng | z <- zs]
         []     ||  ys             =  ys
         xs     ||  []             =  xs
         (x:xs) || (y:ys)  | x==y  =  x : (xs || ys)
                           | x<y   =  x : (xs || (y:ys))
                           | y<x   =  y : (ys || (x:xs))

示例用法

 Prelude Hamming> take 10 $ dropWhile (< 1000) $ genHamming [2,3,5]
 [1000,1024,1080,1125,1152,1200,1215,1250,1280,1296]
 Prelude Hamming>
于 2017-09-25T16:02:39.497 回答
3

Haskell 代码，如本答案所示，

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

有效地从（以上）给定值开始可能是一个有趣的挑战。此答案底部的直接切片生成代码可以作为起点。

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

~> take 10 $ dropWhile (< 100) $ hamm [2,3,5,7]
[100,105,108,112,120,125,126,128,135,140]
于 2017-09-27T10:05:36.913 回答
1

因为我们的应用程序是用 python 编写的，所以我想出了以下我想分享的实现：

def powers(x):
    y = x
    while True:
        yield y
        y *= x


def products(factors):
    y0 = factors[0]
    if len(factors) == 1:
        yield from powers(y0)
    else:
        yield y0
        g1 = products(factors)
        y1 = y0 * next(g1)
        g2 = products(factors[1:])
        y2 = next(g2)
        while True:
            if y1 < y2:
                yield y1
                y1 = y0 * next(g1)
            else:
                yield y2
                y2 = next(g2)


if __name__ == "__main__":
    import itertools
    for n in itertools.islice(products([2, 3, 5, 7]), 10**6):
        print(n)

毫无疑问，可以改进对生成器的递归使用，但实际上性能对于我们的应用程序来说已经足够好了。除此之外，我仍然对如何有效地从给定的最小值开始感兴趣，正如 Will Ness 的回答中提到的那样。感谢所有做出贡献的人。

于 2017-10-14T10:25:26.367 回答
1

您可能还想在输出中包含 2^0 * 3^0 * 5^0 * 7^0 = 1。

做到这一点的方法是使用优先级队列。如果k在序列中，则 2 k、 3 k、 5 k和 7 k也是。从 1 开始输出，然后将 2、3、5 和 7 添加到优先级队列中。从队列顶部弹出 2 并将 2*2=4、2*3=6、2*5=10 和 2*7=14 添加到队列中；此时的队列将包含 3、4、5、6、7、10 和 14。从队列顶部弹出 3 并添加 3*2=6、3*3=9、3*5=15 和 3 *7=21 到队列中。等等。

你会发现很多元素是重复的；例如，在上面的示例中，我们两次将 6 添加到优先级队列中。您可以添加重复项，并在每次弹出队列时检查该元素是否与序列的前一个成员相同，或者您可以在队列中保留单独的项目列表并避免首先添加重复项。

我在我的博客中讨论了一个只包含不同元素的优先级队列。

于 2017-09-25T14:32:55.473 回答
1

每个大于 1 的整数都是“素数集”的乘积，因为它是其素数因子的乘积。从您想要的最小数字开始并删除所有在您的初始集合中没有主要因素的数字可能会更容易。继续该过程，直到您的结果集足够大。实际上，您正在做一个修改后的埃拉托色尼筛法，删除所有不在初始集合中的素数倍数。

于 2017-09-25T16:38:51.403 回答
0

由于每个素数都允许出现多次，所以序列是无限的。所以我们不能生成所有产品然后对它们进行排序。我们必须迭代地生成序列。

如果a是序列的成员，那么{2*a, 3*a, 5*a ... n*a}也将是序列的成员，稍后出现。

所以，我想到的算法是有一个（排序的，无重复的）下一个序列成员的缓冲区。我们提取并呈现最小值并将其所有倍数插入缓冲区。

由于很难预测起始数字的缓冲区内容x，因此该算法应该从头开始并忽略结果，直到它们达到x阈值。

于 2017-09-25T14:41:33.713 回答
0

为此，我想到了两种算法。首先，您可以计算数字之间所有可能的产品，然后对它们进行排序。尽管这似乎是一种幼稚的方法，但您可以通过“记住”最后一个乘积、除以一个数字并在其位置乘以不同的数字来加快速度。如果使用正确的排列顺序（查看格雷码），您可以最大限度地减少总乘法，这将大大减少必要的操作次数。

另一方面，您可以做的是计算所有原始数字的集合，（两个）原始数字对的乘积集合，3 的乘积集合......等等。然后您可以对每个单独的集合进行排序（这应该不难确保它们几乎已经排序），然后将集合合并到一个排序的产品列表中。这将需要更多的操作，但最终会导致一个几乎排序的列表，这可能需要更少的时间来构建整体。

另一种算法是取所有感兴趣的素数的乘积，并将其称为 P。构造另一个所有原始素数平方的列表。现在，循环直到 P 的所有数字，并测试它们是否可以被素数平方数组中的任何值整除。如果是，就把它们扔掉。如果没有，则将它们添加到输出数组。您可以通过仅测试直到 sqrt(i) 的可分性来优化这一点，其中 i 是 for 循环中的迭代。不过，这仍然可能比上述方法慢。

于 2017-09-25T13:01:53.957 回答