按顺序查找一组大于 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

为此想到了两种算法。首先，您可以计算数字之间所有可能的产品，然后对它们进行排序。尽管这似乎是一种幼稚的方法，但您可以通过 'remembering' 最后一个乘积来加快速度，除以一个数字，然后乘以一个不同的数字。这将大大减少必要的操作次数，如果你的排列顺序正确（查看 Gray Codes）你可以最小化总乘法。

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

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

Answer 2

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

执行此操作的方法是使用优先级队列。如果 k 在序列中，那么 2k, 3k, 5k 和 7k。从 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 添加到优先级队列中。您可以添加重复项，并在每次弹出队列时检查该元素是否与序列中的前一个成员相同，或者您可以在队列中保留一个单独的项目列表，并避免首先添加重复项。

我讨论了一个只包含 my blog 处不同元素的优先级队列。

Answer 3

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

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

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

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

Answer 4

（编辑：让它按升序生成所有产品；让用户根据需要过滤它们。这是一个普遍的 Hamming numbers 问题）

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>

Answer 5

每个大于 1 的整数都是 'set of primes' 的乘积，因为它是其质因数的乘积。从您想要的最小数字开始并剔除所有不在初始集合中的质因数可能更容易。继续这个过程，直到你的结果集足够大。实际上，您正在执行修改后的埃拉托色尼筛法，删除不在初始集合中的所有素数倍数。

Answer 6

一个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]

Answer 7

因为我们的应用程序是用 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 的中提到的那样。感谢所有贡献者。

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

algorithm to find products of a set of primes, in order, greater than x

algorithm

primes

number-theory

hamming-numbers

smooth-numbers