使用一组素数按升序生成整数

我有一组素数，我必须仅使用这些素数因子按升序生成整数。

例如，如果集合是p= {2, 5} 那么我的整数应该是 1, 2, 4, 5, 8, 10, 16, 20, 25, …

有没有高效的算法来解决这个问题呢？

删除号码并重新插入它的所有倍数（由集合中的素数）进入优先级队列是wrong（就问题的意义而言） - 即它产生正确的序列，但是低效地 so.

它在两个方面是低效的——首先，生产过剩序列;其次，每个 PriorityQueue 操作都会产生额外的成本（操作remove_top and insert通常不是两者兼而有之O(1)，当然不在任何基于列表或树的 PriorityQueue 实现中）。

高效的O(n)算法在生成序列时维护返回序列本身的指针，以查找并附加下一个数字O(1)时间。在伪代码中：

  return array h where
    h[0]=1; n=0; ps=[2,3,5, ... ]; // base primes
    is=[0 for each p in ps];       // indices back into h
    xs=[p for each p in ps]        // next multiples: xs[k]==ps[k]*h[is[k]]
    repeat:
      h[++n] := minimum xs
      for each ref (i,x,p) in (is,xs,ps):
        if( x==h[n] )
          { x := p*h[++i]; }       // advance the minimal multiple/pointer

For each minimal multiple it advances its pointer, while at the same time calculating its next multiple value. This too effectively implements a PriorityQueue but with crucial distinctions - it is before the end point, not after; it doesn't create any additional storage except for the sequence itself; and its size is constant (just k numbers, for k base primes) whereas the size of past-the-end PriorityQueue grows as we progress along the sequence (in the case of Hamming sequence, based on set of 3 primes, as n^2/3, for n numbers of the sequence).

经典Haskell 中的汉明序列本质上是相同的算法：

h = 1 : map (2*) h `union` map (3*) h `union` map (5*) h

union a@(x:xs) b@(y:ys) = case compare x y of LT -> x : union  xs  b
                                              EQ -> x : union  xs  ys
                                              GT -> y : union  a   ys

我们可以生成平滑数字 for 随意的基础素数使用foldi函数（参见维基百科) 将列表折叠在树状的为了提高效率，创建固定大小的比较树：

smooth base_primes = h   where       -- strictly increasing base_primes  NB!
    h = 1 : foldi g [] [map (p*) h | p <- base_primes]
    g (x:xs) ys = x : union xs ys

foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))
 
pairs f (x:y:t)  = f x y : pairs f t
pairs f t        = t

It is also possible to directly calculate a slice of Hamming sequence around its nth member in O(n^2/3) time, by direct enumeration of the triples and assessing their values through logarithms, logval(i,j,k) = i*log 2+j*log 3+k*log 5. This Ideone.com test entry calculates 1 billionth Hamming number in 1.12 0.05 seconds _{(2016-08-18: main speedup due to usage of Int instead of the default Integer where possible, even on 32-bit; additional 20% thanks to the tweak suggested by @GordonBGood, bringing band size complexity down to O(n^1/3)).}

这在中进行了更多讨论这个答案在那里我们还可以找到它的完整归属：

slice hi w = (c, sortBy (compare `on` fst) b) where  -- hi is a top log2 value
  lb5=logBase 2 5 ; lb3=logBase 2 3                  -- w<1 (NB!) is (log2 width)
  (Sum c, b) = fold                                  -- total count, the band
      [ ( Sum (i+1),                                 -- total triples w/this j,k
          [ (r,(i,j,k)) | frac < w ] )               -- store it, if inside the band
        | k <- [ 0 .. floor ( hi   /lb5) ],  let p = fromIntegral k*lb5,
          j <- [ 0 .. floor ((hi-p)/lb3) ],  let q = fromIntegral j*lb3 + p,
          let (i,frac) = pr  (hi-q)      ;       r = hi - frac    -- r = i + q
      ]    -- (sum . map fst &&& concat . map snd)
  pr = properFraction 

This can be generalized for k base primes as well, probably running in O(n^(k-1)/k) time.

(see 这个SO条目为了以后的重要发展。还，这个答案很有趣。和另一个相关答案.)