使用一组素数按升序生成整数
我有一组素数，我只能使用这些素数因子按递增顺序生成整数。
例如，如果集合是p = {2,5}，那么我的整数应该是1,2,4,5,8,10,16,20,25 …
有没有有效的algorithm来解决这个问题？
基本思想是1是集合中的一员，对于集合n中的每一个成员， 2n和5n也是集合中的成员。 因此，您从输出1开始，并将2和5推入优先级队列。 然后，重复popup优先级队列的前一项，如果与前一次输出不一样，则输出，并将优先级队列中的数字推入2倍5倍。
谷歌的“汉明号码”或“常规号码”或去A003592了解更多。
—–添加后期—–
我决定在午餐时间花几分钟时间编写一个程序来实现上述algorithm，使用Scheme编程语言。 首先， 这里是使用配对堆algorithm的优先级队列的库实现：
(define pq-empty '()) (define pq-empty? null?) (define (pq-first pq) (if (null? pq) (error 'pq-first "can't extract minimum from null queue") (car pq))) (define (pq-merge lt? p1 p2) (cond ((null? p1) p2) ((null? p2) p1) ((lt? (car p2) (car p1)) (cons (car p2) (cons p1 (cdr p2)))) (else (cons (car p1) (cons p2 (cdr p1)))))) (define (pq-insert lt? x pq) (pq-merge lt? (list x) pq)) (define (pq-merge-pairs lt? ps) (cond ((null? ps) '()) ((null? (cdr ps)) (car ps)) (else (pq-merge lt? (pq-merge lt? (car ps) (cadr ps)) (pq-merge-pairs lt? (cddr ps)))))) (define (pq-rest lt? pq) (if (null? pq) (error 'pq-rest "can't delete minimum from null queue") (pq-merge-pairs lt? (cdr pq)))) 现在的algorithm。 函数f需要两个参数，一个是设置ps中的数字列表，另一个是从输出头开始输出的项目数量。 algorithm稍有改变; 通过按1来初始化优先级队列，然后提取步骤开始。 variablesp是前一个输出值（最初为0）， pq是优先级队列， xs是输出列表，以相反的顺序累加。 代码如下：
(define (f ps n) (let loop ((nn) (p 0) (pq (pq-insert < 1 pq-empty)) (xs (list))) (cond ((zero? n) (reverse xs)) ((= (pq-first pq) p) (loop np (pq-rest < pq) xs)) (else (loop (- n 1) (pq-first pq) (update < pq ps) (cons (pq-first pq) xs))))))
对于那些不熟悉Scheme的人来说， loop是一个recursion调用的本地定义的函数，而cond是if-else链的头部。 在这种情况下，有三个cond子句，每个子句都有一个谓词和随后的结果，随后对谓词为真的第一个子句进行评估。 谓词(zero? n)终止recursion并以正确的顺序返回输出列表。 谓词(= (pq-first pq) p)表示先前输出了优先级队列的当前头部，因此在第一个项目之后通过优先级队列的其余部分重复跳过。 最后，总是为真的else谓词标识一个新输出的数字，所以递减计数器，将当前的优先级队列头保存为新的先前值，更新优先级队列以添加新的当前号码，并将当前的优先级队列头插入到累加输出中。
由于更新优先级队列以添加当前编号的新子节点并不重要，因此将该操作提取到一个单独的函数：
(define (update lt? pq ps) (let loop ((ps ps) (pq pq)) (if (null? ps) (pq-rest lt? pq) (loop (cdr ps) (pq-insert lt? (* (pq-first pq) (car ps)) pq)))))
函数遍历ps集的元素，依次插入优先级队列; 当ps列表耗尽时， if返回更新的优先级队列，减去其旧头。 recursion步骤用cdr剥离ps列表的头部，并将优先级队列的头部和ps列表的头部的乘积插入到优先级队列中。
这里有两个algorithm的例子：
> (f '(2 5) 20) (1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250) > (f '(2 3 5) 20) (1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36)
删除一个数字并将其所有倍数 （通过集合中的素数）重新插入到优先级队列中是错误的 （就问题的意义而言） – 即它产生正确的序列，但效率低下 。
这在两个方面是低效的 – 首先，它过度生产序列; 其次，每个PriorityQueue操作都会产生额外的成本（操作remove_top和insert通常都不是O（1） ，当然不在任何基于列表或树的PriorityQueue实现中）。
有效的O（n）algorithm将指针返回到正在生成的序列本身中，以查找并附加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 (i,x,p) in (is,xs,ps): if( x==h[n] ) { x := p*h[++i]; } // advance the minimal multiple/pointer
对于每个最小的倍数，它提前它的指针，同时计算它的下一个倍数值。 这个过程有效地实现了一个PriorityQueue，但是具有关键的区别 – 它是在结束点之前 ，而不是在之后; 除了序列本身之外，它不会创build任何额外的存储空间; 并且其大小是恒定的（对于k个基本素数只是k个数字），而随着我们沿着序列前进，过去末端的PriorityQueue的大小增加（在汉明序列的情况下，基于3个素数的集合，为n 2 / 3 ，对于n个序列）。
Haskell中经典的Hamming序列基本上是相同的algorithm：
h = 1 : map (2*) h `union` map (3*) h `union` map (5*) h union a@(x:xs) b@(y:ys) = case compare xy of LT -> x : union xs b EQ -> x : union xs ys GT -> y : union a ys
我们可以使用foldi函数（请参阅Wikipedia ）以树状方式折叠列表来生成任意基本素数的平滑数字以提高效率，从而创build一个固定大小的比较树：
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 fz [] = z foldi fz (x:xs) = fx (foldi fz (pairs f xs)) pairs f (x:y:t) = fxy : pairs ft pairs ft = t
通过直接列举三元组并通过对数来评估它们的值， logval(i,j,k) = i*log 2+j*log 3+k*log 5可以直接计算O（n 2/3 ）时间内围绕其第n个成员的Hamming序列片段logval(i,j,k) = i*log 2+j*log 3+k*log 5 。 这个Ideone.comtesting条目在1.12 0.05秒（2016-08-18：由于使用Int而不是默认Integer （即使在32位）时使用主加速，计算十亿分之一的汉明数字 ：由于调整，额外的20％由@GordonBGoodbuild议，将带宽复杂度降至O（n 1/3 ））。
这个问题在这个答案中有更多的讨论，我们也可以find它的全部属性：
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 ）时间。
看到这个SO入门的重要后续发展。 另外， 这个答案很有趣。 和另一个相关的答案 。
这个二维探索algorithm并不精确，但是对于前25个整数，然后混合了625和512。
n = 0 exp_before_5 = 2 while true i = 0 do output 2^(n-exp_before_5*i) * 5^Max(0, n-exp_before_5*(i+1)) i <- i + 1 loop while n-exp_before_5*(i+1) >= 0 n <- n + 1 end while
根据user448810的回答，这是一个使用STL的堆和向量的解决scheme。
现在，堆通常会输出最大的值，所以我们将数字的负值存储为解决方法（因为a>b <==> -a<-b ）。
#include <vector> #include <iostream> #include <algorithm> int main() { std::vector<int> primes; primes.push_back(2); primes.push_back(5);//Our prime numbers that we get to use std::vector<int> heap;//the heap that is going to store our possible values heap.push_back(-1); std::vector<int> outputs; outputs.push_back(1); while(outputs.size() < 10) { std::pop_heap(heap.begin(), heap.end()); int nValue = -*heap.rbegin();//Get current smallest number heap.pop_back(); if(nValue != *outputs.rbegin())//Is it a repeat? { outputs.push_back(nValue); } for(unsigned int i = 0; i < primes.size(); i++) { heap.push_back(-nValue * primes[i]);//add new values std::push_heap(heap.begin(), heap.end()); } } //output our answer for(unsigned int i = 0; i < outputs.size(); i++) { std::cout << outputs[i] << " "; } std::cout << std::endl; }
输出：
1 2 4 5 8 10 16 20 25 32
