1

説明：

正の整数mは、mが素数pのq乗として表現できる場合にのみ純粋な数と呼ばれます（q> = 1）。ここであなたの仕事は簡単です、与えられた正の整数kに対して、k番目の純粋な数を見つけてください。

入力：

入力は複数のテストケースで構成されています。テストケースごとに、正の整数k（k <5,000,000）が含まれます。ファイルの終わりまで処理します。

出力：

テストケースごとに、k番目の純粋な数値を1行で出力します。答えが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問題の説明に注意してください：すべての素数は純粋な数です）、そのためにある種のふるいを使用する必要があります（エラトステネスのふるいはそれを調べます） 。

おそらく素数冪を残すようにふるいを適応させることもできますが、通常のふるい分けをしてから素数を元に戻すのにそれほど時間はかからないと思います。素数冪を計算するだけで済みます。ここで、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」としてマークされた非純粋な（素数）数。

各出力について、出力結果[インデックス]内にある場合は配列範囲をチェックし、そうでない場合は-1にする必要があります。

于 2013-01-29T14:32:07.267 に答える