1

描述：

当且仅当 m 可以表示为素数 p (q >= 1) 的 q 次方时，正整数 m 被称为纯数。在这里你的工作很简单，对于给定的正整数 k，找到第 k 个纯数。

输入：

输入由多个测试用例组成。对于每个测试用例，它包含一个正整数 k (k<5,000,000)。处理到文件末尾。

输出：

对于每个测试用例，在一行中输出第 k 个纯数。如果答案大于 5,000,000，则输出 -1。

样本输入：

1

100

400000

样本输出：

2

419

-1

原文页面：http ://acm.whu.edu.cn/learn/problem/detail?problem_id=1092

谁能给我一些关于解决这个问题的建议？

4

2 回答 2

4

你已经算出了所有的纯数字，这是棘手的部分。对小于 500 万的排序，然后在结果数组中依次查找每个输入。

要进行优化，您需要有效地找到最多 500 万的所有素数（q >= 1问题描述中请注意：每个素数都是纯数），您需要为此使用某种筛子（Erathosthenes 筛子就可以了，查一下） .

您可能可以调整筛子以保留素数的幂，但我希望正常筛分并重新输入幂不会花费很长时间。您只需要计算素数 p 的幂，其中 p <= 的平方根500 万，即 2236，因此与找到素数相比，这应该不会花费很长时间。

用筛子找到数字后，您不再需要对它们进行排序，只需将标记的值从筛子复制到新数组中。

现在查看了您的实际代码：您的 QuickSort 例程是可疑的。它对已经排序的数据表现不佳，并且您的数组中将包含排序数字。改为尝试qsort，或者如果您应该自己做所有事情，那么您需要阅读快速排序的枢轴选择。

于 2013-01-29T14:09:23.860 回答
0

尝试以下方法：

static void Main(string[] args)
{

    int max = 5000000;
    int[] dp = new int[max];
    for (int i = 2; i < max; i++)
    {
        if (dp[i] == 0)
        {
            long t = i;
            while (t < max)
            {
                dp[t] = 1;
                t *= i;
            }
            int end = max / i;
            for (int j = 2; j < end; j++)
                if (dp[i * j] == 0)
                    dp[i * j] = 2;
        }
    }

    int[] result = new int[348978];
    int pointer = 1;
    for (int i = 2; i < max; i++)
    {
        if (dp[i] == 1)
            result[pointer++] = i;
    }
}

放入数组为“1”标记的纯数字。作为“2”标记的非纯（素数）数字。

对于每个输出检查数组范围，如果它在输出结果 [index]内，如果不是输出应该是 -1。

于 2013-01-29T14:32:07.267 回答