Description:
A positive integer m is said to a pure number if and only if m can be expressed as q-th power of a prime p (q >= 1). Here your job is easy, for a given positive integer k, find the k-th pure number.
Input:
The input consists of multiple test cases. For each test case, it contains a positive integer k (k<5,000,000). Process to end of file.
Output:
For each test case, output the k-th pure number in a single line. If the answer is larger than 5,000,000, just output -1.
Sample input:
1
100
400000
Sample output:
2
419
-1
原始页面:http://acm.whu.edu.cn/learn/problem/detail?problem_id=1092
谁能给我一些解决方案的建议？
最佳答案
您已经计算出所有纯数字，这是棘手的部分。对小于 500 万的进行排序，然后在结果数组中依次查找每个输入。
要进行优化，您需要有效地找到最多 500 万个素数(请注意问题描述中的 q >= 1:每个素数都是纯数)，为此您需要使用一些一种筛子(Erathosthenes 的筛子就可以，查一下)。
您可能会调整筛子以留下素数的幂，但我希望正常筛分不会花很长时间，然后将幂放回原位。您只需计算素数 p 的幂，其中 p <= the 500 万的平方根，即 2236，因此与寻找素数相比，这应该不会花费很长时间。
用筛子找到数字后，您不再需要对它们进行排序，只需将标记的值从筛子复制到新数组即可。
现在查看您的实际代码:您的 QuickSort 例程值得怀疑。它对已经排序的数据表现不佳，并且您的数组中将包含一系列排序的数字。请改用 qsort，或者如果您应该自己做所有事情，那么您需要阅读有关快速排序的枢轴选择。
关于c - 算法 - 查找纯数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14584712/