3

数値の範囲を並べ替える必要があります。数値は0〜1000の範囲で指定できます。ユーザーは、0〜1000の範囲の数値を入力します。たとえば、たとえば0〜>500と入力します。

私の目標は、指定された範囲内のすべての数値を取得し、4つの可能な除数（1とそれ自体を含む）しかないその範囲内のすべての数値を出力することです。

このようなアルゴリズムを使用する必要があるのか​​、それとも4で割り切れる1から1000までのすべての数値を含む配列をチェックしてintにする必要があるのか​​、疑問に思っています（したがって、配列には1から1000がありません。その範囲内の数値は4回しか割り切れません。その配列にすべての可能な除数を追加するには、手動で作業する必要があります）。

私はそれを効率的にすることを目指していますが、そのようなアルゴリズムを使用することがこれに対して非常に高速であるかどうかはわかりません。

4

1 に答える 1

6

2 つの素数edit: または素数の 3 乗の積である数値を探しています。数値が小さいので、2 から 500 までの素数の短い表を作成するだけで済みます。次に、2 から始めて、上限を超えるまで、各素数にその上の各素数を掛けます。

編集：これは宿題ですか？もしそうなら、私はおそらくすでに言い過ぎました。そうでない場合、答えが意味をなさない場合は、コードまたは疑似コードを提供できます。

編集: ありがとう、ダニエル・フィッシャー: 素数の立方体を見逃していました。これらを確認して、外側のループに含めることができます。(素数にその上の各素数を掛ける前に、その立方体が目的の範囲内にあるかどうかを確認してください。)

一般的：

for ( p1 is a prime in your list, except for the last) {
    if p1 cubed is in your range, add it to the answer
    for (p2 is a prime in your list greater than p1) {
        if p2*p1 is in your range, add it to the answer
        //optimization: break when you know you won't find any more
    }
}
// optimization: calculate the ranges of p1 and p2 to be included 
// before you start each loop
// (probably only worthwhile if you raise the limit to something 
// much larger than 1000)

確かに、このスケールの数値には十分な速さです。1 ミリ秒未満で完了しました (0 から 1000 までの 292 の数値を見つけるために。ハードコードされた素数を使用しました --- この範囲の入力には 95 個しか必要ありません)。

于 2012-04-22T17:36:02.377 に答える