我们怎样才能打印出所有完美的权力，可以重新psented为64位长整数$ P $：4，8，9，16，25，27，......一个完美的电源是一个数字，可以写为AB为整数a和b≥2。 这不是一个家庭作业的问题，我发现它在算法设计书的面试问题部分。提示，本章是基于优先级队列。

How can we print out all perfect powers that can be represented as 64-bit long integers: 4, 8, 9, 16, 25, 27, .... A perfect power is a number that can be written as ab for integers a and b ≥ 2. It's not a homework problem, I found it in job interview questions section of an algorithm design book. Hint, the chapter was based on priority queues.

大多数的想法我是二次性的，即不断寻找权力，直到他们停止装修的64位，但是这不是面试官会寻找。此外，我无法理解怎么会PQ的帮助在这里。

Most of the ideas I have are quadratic in nature, that keep finding powers until they stop fitting 64 bit but that's not what an interviewer will look for. Also, I'm not able to understand how would PQ's help here.

推荐答案

使用一个小的优先级队列，每个电源一个条目，是一种合理的方式列出数字。请参见下面的蟒蛇code。

Using a small priority queue, with one entry per power, is a reasonable way to list the numbers. See following python code.

import Queue             # in Python 3 say:  queue
pmax, vmax = 10, 150
Q=Queue.PriorityQueue(pmax)
p = 2
for e in range(2,pmax):
    p *= 2
    Q.put((p,2,e))

print 1,1,2
while not Q.empty():
    (v, b, e) = Q.get()
    if v < vmax:
        print v, b, e
        b += 1
        Q.put((b**e, b, e))

使用PMAX，VMAX作为code以上时，它产生以下输出。对于所提出的问题，将 PMAX 和 VMAX 与 64 和 2 ** 64 。

With pmax, vmax as in the code above, it produces the following output. For the proposed problem, replace pmax and vmax with 64 and 2**64.

1 1 2
4 2 2
8 2 3
9 3 2
16 2 4
16 4 2
25 5 2
27 3 3
32 2 5
36 6 2
49 7 2
64 2 6
64 4 3
64 8 2
81 3 4
81 9 2
100 10 2
121 11 2
125 5 3
128 2 7
144 12 2

在这种方法的复杂度为O（VMAX ^ 0.5 *日志（p最大））。这是因为完全平方数是显性的完美的立方体，第四大国，数量等，并为每平方米我们做O（日志（p最大））工作 GET 和把队列操作。对于更高的权力，我们计算的时候做O（日志（p最大））工作 B **è。

The complexity of this method is O(vmax^0.5 * log(pmax)). This is because the number of perfect squares is dominant over the number of perfect cubes, fourth powers, etc., and for each square we do O(log(pmax)) work for get and put queue operations. For higher powers, we do O(log(pmax)) work when computing b**e.

在 VMAX，PMAX = 64，2 ** 64 ，将有大约2 *（2 ^ 32 + 2 ^ 21 + 2 ^ 16 + 2 ^ 12 + ...）队列操作，即约2 ^ 33队列欢声笑语。

When vmax,pmax =64, 2**64, there will be about 2*(2^32 + 2^21 + 2^16 + 2^12 + ...) queue operations, ie about 2^33 queue ops.

添加了注意事项：的这记地址cf16的评论，一句话而已，我不认为完美的方块数是显性完美的立方体，第四大国，数量等他们都是无穷的。但是，是的，如果我们考虑有限集。这是事实，在事物的整体数学方案中，基数是相同的。也就是说，如果 P（j）条是集所有的J '个整数的权力，那么基数 P（j）条== P（K）所有整数 J，K＆GT; 0 。任何两组权力元件可投入1-1彼此对应。

Added note: This note addresses cf16's comment, "one remark only, I don't think "the number of perfect squares is dominant over the number of perfect cubes, fourth powers, etc." they all are infinite. but yes, if we consider finite set". It is true that in the overall mathematical scheme of things, the cardinalities are the same. That is, if P(j) is the set of all j'th powers of integers, then the cardinality of P(j) == P(k) for all integers j,k > 0. Elements of any two sets of powers can be put into 1-1 correspondence with each other.

然而，当计算完美权力的升序排列的，无论有多少计算，有限与否，提供正方形的工作占主导地位，对任何其他权力。对于任何给定的 X 的，完美的 K 的日在该地区的力量密度的 X 的指数下降为 K 的增加​​。由于 X 的增加​​，完善​​的 K 的日的密度在该地区大国的 X 的是成正比的（ X 的 1 / K ）/ X 的，因此第三大国，第四大国，等成为微乎其微罕见相比，广场的的 X 的增加了。

Nevertheless, when computing perfect powers in ascending order, no matter how many are computed, finite or not, the work of delivering squares dominates that for any other power. For any given x, the density of perfect kth powers in the region of x declines exponentially as k increases. As x increases, the density of perfect kth powers in the region of x is proportional to (x1/k)/x, hence third powers, fourth powers, etc become vanishingly rare compared to squares as x increases.

作为具体例，除1E8和1E9的数量之间完美的权力（2; 3; 4; 5; 6）次方大约是（21622; 535; 77; 24; 10）。有超过30倍1E8和1E9之间尽可能多平方比有比正方形任何更高的权力实例。这里是完美的正方形两个数字之间的数，VS的较高完善权力的数量之比：10 10，10 15，r≈301; 10 15，10 20，r≈2K; 10 20-10²⁵，r≈15K; 10²⁵-10³⁰，r≈100K。总之，作为的 X 的增加​​，广场占据越来越多的在完善权力交付升序进行排序。

As a concrete example, among perfect powers between 1e8 and 1e9 the number of (2; 3; 4; 5; 6)th powers is about (21622; 535; 77; 24; 10). There are more than 30 times as many squares between 1e8 and 1e9 than there are instances of any higher powers than squares. Here are ratios of the number of perfect squares between two numbers, vs the number of higher perfect powers: 10¹⁰–10¹⁵, r≈301; 10¹⁵–10²⁰, r≈2K; 10²⁰–10²⁵, r≈15K; 10²⁵–10³⁰, r≈100K. In short, as x increases, squares dominate more and more when perfect powers are delivered in ascending order.