algorithm - 使用一组质数按升序生成整数

Question

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

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

有没有什么高效的算法可以解决这个问题？

Answer 1

删除一个数字并将它的所有倍数(通过集合中的质数)重新插入优先级队列是错误的(在问题的意义上)- 即它生成正确的序列，但效率低下。

它在两个方面效率低下 - 首先，它过度生产序列；其次，每个 PriorityQueue 操作都会产生额外的成本(操作 remove_top 和 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

对于每个最小倍数，它会推进其指针，同时计算其下一个倍数。这太有效地实现了 PriorityQueue，但具有重要的区别 - 它在终点之前，而不是之后；除了序列本身，它不会创建任何额外的存储；并且它的大小是恒定的(只有 k 个数，对于 k 个基素数)而尾部 PriorityQueue 的大小随着我们沿着序列前进(在这种情况下汉明序列，基于一组 3 个素数，如 n^2/3，对于 n 个数顺序)。

---

经典Hamming sequence in 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

我们可以生成 smooth numbers对于 任意 基素数，使用 foldi 函数(参见 Wikipedia )以树状方式折叠列表以提高效率，创建一个固定的大小比较树:

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

---

也可以在 O(n^2/3) 时间，通过直接枚举三元组并通过对数评估它们的值，logval(i,j,k) = i*log 2+j*log 3+k*log 5。这Ideone.com test entry计算 1 billionth Hamming number在 1.12 0.05 秒内 _{(2016-08-18:由于使用 Int 而不是默认的 Integer，主要加速 在可能的情况下，甚至在 32 位上；由于 @GordonBGood 建议的调整，额外 20%，将带大小复杂度降低到 O(n^1/3))。}

这在 this answer 中有更多讨论我们还可以在其中找到它的完整属性:

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 

这也可以推广到 k 个基素数，可能在 O(n^(k-1)/k) 时间内运行.

---

(请参阅 this SO entry 了解重要的后期开发。另外，this answer 很有趣。还有另一个 related answer。)