0

私は数ヶ月間、楽しみのためにJavaを使用してオイラーの問題を解決しています。多くの場合、ヒープサイズが私を制限しているので、他の人がこの行き止まりで苛立たしい終わりに達したときに何をするのか疑問に思いました.

良い例は、問題 " http://projecteuler.net/problem=432 " で、数ミリ秒で 10^6 を解決するきちんとした関数がありますが、要求された値 (10^ 11) サイズ 10^11 の整数配列が必要なためです。

編集:質問を明確にするために。大きな数をふるいにかける方法はありますか?たとえば、10^10 より大きい最初の素数を見つけなければならないとしたら、どうしますか?

4

2 に答える 2

0

本当に大きな素数の場合、ふるい配列の最大長が Integer.MAX_VALUE によって制限されているため、エラトステネスのふるいから取得することはできません。

最も簡単な方法でそれらを計算できます-

prime(N) = [0, sqrt(N)] 内のすべての素数が N の素因数でない場合。

そして、計算したすべての大きな素数を 1 つまたは複数のファイルに保存します。一度それを行ってから、それらを再利用してください。大きな素数を必要とするオイラー問題を実行するときは、最初にこれらの素数をファイルからメモリにロードします。

于 2013-07-23T18:45:39.687 に答える