算法 - 查找纯数字

Question

描述：

正整数

m

被称为纯数当且仅当

m

可以 表示为素数

q

的

p

次方 (

q

>= 1)。 在这里你的工作很简单， 对于给定的正整数

k

，找到第

k

个纯数。

输入：

输入由多个测试用例组成。对于每个测试用例， 包含正整数

k

(k<5,000,000). Process to end of file.

输出：

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

输入示例：

1

100

400000

输出示例：

2

419

-1

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

任何人都可以给我一些解决此问题的建议吗？

Answer 1

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

为了优化，你需要有效地找到最多 500 万个素数（注意问题描述中的

q >= 1

：每个素数都是纯数），为此你需要使用某种筛子（埃拉托斯特尼筛子就可以，查一下）。

您可能可以调整筛子以保留素数的幂，但我预计正常筛选然后将幂放回原处不会花费很长时间。您只需计算素数 p 的幂，其中 p <= the square root of 5 million, which is 2236, so this shouldn't take long compared with finding the primes.

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

现在查看您的实际代码：您的 QuickSort 例程值得怀疑。它对于已经排序的数据表现很差，并且您的数组中将包含一系列已排序的数字。请尝试

qsort

，或者如果您应该自己完成所有事情，那么您需要阅读快速排序的枢轴选择。

Answer 2

尝试以下方法：

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”标记非纯（质数）数字。

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