数字的完美幂，可以容纳64位大小的整数(使用优先级队列)
数字的完美幂，可以容纳64位大小的整数(使用优先级队列)
提问于 2012-10-19 13:19:49
我们如何打印出可以表示为64位长整数的所有完美幂: 4，8，9，16，25，27，...完美幂是一个整数a和b≥2可以写成ab的数字。这不是一个家庭作业问题，我在一本算法设计书的求职面试问题部分找到了它。提示，本章基于优先级队列。
我的大多数想法本质上都是二次的，它们一直在寻找力量，直到它们不再适合64位，但这不是面试官会寻找的。另外，我不能理解PQ在这里会有什么帮助。
回答 1
Stack Overflow用户
发布于 2012-10-19 13:37:20
我认为优先级队列有意义的唯一方法是，您希望在数字可用时以严格递增的顺序打印它们，当然不打印任何数字两次。因此，您可以从一个素数生成器开始(它使用eratosthenes筛子或一些更智能的技术来生成序列2，3，5，7，11，...)。首先将表示2^2 =4的三元组放到队列中。然后重复一个过程，从队列中删除最小的项(具有最小求幂结果的三元组)，打印它，将指数加1，然后将其放回队列中(其优先级由新求幂的结果确定)。您可以将这个过程与一个根据需要生成新素数的过程交错(在输出p^2之前的某个时候)。
由于我们最大的指数基数可能是2^32 ( 2^32 )^2 = 2^64，因此队列中元素的数量不应该超过小于2^32的素数的数量，即evidently 203,280,221，我猜这是一个容易处理的数字。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12967810
复制相关文章
相似问题
腾讯云开发者
