問題タブ [primes]

そのため、私は自分のことをかなり初心者のプログラマーと呼んでいます。学校教育では主にハードウェアに集中しており、コンピューター サイエンスのコースはあまり多くありませんでした。

そこで、Project Euler の問題 7 を解決しました。

最初の 6 つの素数 (2、3、5、7、11、13) をリストすると、6 番目の素数が 13 であることがわかります。

10001番目の素数は何ですか?

Javaで問題なくこれを解決できましたが、ソリューションを実行すると、実行に8秒かかりました。数学的な観点ではなく、プログラミングの観点からこれをどのように最適化できるか疑問に思っていました。

配列がループしているか、主に while ステートメントが処理時間を消費していますか? そして、これをどのように最適化できますか? 繰り返しますが、派手な数式を探しているわけではありません..ソリューションスレッドにはそれらがたくさんあります.

スポイラー私の解決策を以下に示します。

}

プロジェクトオイラーの問題50を解決しようとしています。私に答えを与えたり、私のためにそれを解決したりしないでください。この特定の質問に答えてみてください。

目標は、100万未満の素数に追加される連続する素数の最長の合計を見つけることです。n以下の素数をすべて見つけるためにふるいを書き、それが正しいことを確認しました。次に、次の方法を使用して、連続する素数の各サブセットの合計を確認します。

空のリストがありますsums。素数ごとに、の各要素に追加しsumsて新しい合計を確認してから、に素数を追加しますsums。

これはPythonです

check()100万未満の2つ以上の連続する素数のすべての合計を要求したかどうかを知りたい

問題は、21個の連続する素数の合計として書くことができる素数953があることを示していますが、私はそれを見つけていません。

私は最近、私の学校で小さなJavaプログラミングコンテストに参加しました。私のパートナーと私は最初の純粋なoopクラスを終えたばかりで、ほとんどの質問は私たちのリーグから外れていたので、これに落ち着きました（そして私は多少言い換えています）：「入力整数nが与えられた場合、プライムである次のintを返しますその逆も素数です。たとえば、n = 18の場合、31と13は両方とも素数であるため、プログラムは31"を出力する必要があります。.classファイルには、1〜2,000,000,000のすべての可能な数値のテストケースが渡され、有効と見なされるには10秒以内に正解を返す必要がありました。

解決策を見つけましたが、テストケースが大きい場合は、10秒以上かかります。ループの範囲をn、.. 2,000,000,000から下に移動する方法があると確信しています。これは、nが小さい場合にループする必要がある可能性が低いためですが、どちらの方法でも、数値が小さい場合はループを解除します。両方の条件下で素数が見つかります。最初は2、.. nからループしていましたが、それがどれほど大きくても、nの平方根にのみループするという規則を思い出しました。私のプログラムをより効率的にする方法について何か提案はありますか？アルゴリズムの複雑さの分析を扱うクラスはありませんでした。これが私たちの試みです。

コードのフォーマットを間違えた場合は申し訳ありませんが、ここに投稿するのはこれが初めてです。また、出力には各行の後に「＃」が必要でした。これは、ループの後の行が何であるかを示しています。皆さんが提供してくれた助けに感謝します!!!

RosettaCodeで Java の次のコード例を見つけました。

• 私は特にJavaを知りませんが、正規表現自体を除いて、このスニペットのすべての側面を理解しています
• 組み込みの PHP 関数で見られるように、Regex の基本的な知識から高度な知識まで持っています。

.?|(..+?)\\1+素数はどのように一致しますか?

200 万未満のすべての素数の合計を返すプログラムを作成しました。これで何が起こっているのか本当にわかりません。正解が142913828922の場合、答えとして142891895587が得られます。そこにいくつかの素数が欠けているようです。getPrime 関数が想定どおりに機能すると確信しています。以前に数回使用しましたが、正常に動作しました。コードは次のとおりです。

問題

このプロジェクトでは、標準入力から正の整数nを読み取り、最初のn個の素数を出力するJavaプログラムを作成します。m = kdのような整数kが存在する場合、つまりdがmに均等に分割される場合、整数mは非ゼロの整数dで割り切れると言います。同様に、dによる（整数の）除算の余りがゼロの場合、mはdで割り切れます。また、dはmの約数であると言うことでこれを表現します。正の整数pは、その正の約数が1とpのみである場合、素数と呼ばれます。この規則の1つの例外は、素数ではないと見なされる1番自体です。素数ではない正の整数は、合成と呼ばれます。ユークリッドは、素数が無限に多いことを示しました。プライムシーケンスとコンポジットシーケンスは次のように始まります。

素数性について数をテストする方法はたくさんありますが、おそらく最も簡単なのは、単純に試行分割を行うことです。mを2で割ることから始めます。均等に割る場合、mは素数ではありません。それ以外の場合は、3、次に4、次に5などで除算します。任意の点でmが2 dm-1の範囲の数値dで割り切れることがわかった場合は、停止し、mが複合であると結論付けます。それ以外の場合は、mが素数であると結論付けます。一瞬の考えは、それ自体が複合である数dによる試行除算を行う必要がないことを示しています。たとえば、2による試行除算が失敗した場合（つまり、余りがゼロ以外であるため、mが奇数）、4、6、8、または任意の偶数による試行除算も失敗する必要があります。したがって、素数mについて素数をテストするには、m未満の素数で試行除算を行うだけで済みます。さらに、m-1まで行く必要はありません。午後2時の範囲で素数pによるmの試行除算を行うだけで済みます。これを確認するために、m>1が合成であると仮定します。次に、1 <a <m、1 <b <m、およびm=abとなる正の整数aおよびbが存在します。しかし、a>mとb>mの両方の場合、ab> mであり、m=abと矛盾します。したがって、aまたはbのいずれかがm以下である必要があります。

このプロセスをJavaで実装するには、次のシグネチャを使用してisPrime（）という関数を記述します。

この関数は、mが素数であるか合成であるかに応じて、trueまたはfalseを返します。配列引数Pには、テストを実行するのに十分な数の素数が含まれます。具体的には、isPrime（）が呼び出された時点で、配列Pには（少なくとも）午後2時の範囲のすべての素数pが含まれている必要があります。たとえば、素数性についてm = 53をテストするには、2、3、5、および7で連続した試行除算を実行する必要があります。11>53以降はこれ以上進みません。したがって、関数呼び出しisPrime（53、P）の前提条件は、P [0] = 2、P [1] = 3、P [2] = 5、およびP [3]=7です。これらのすべての除算が失敗するため、この場合の戻り値はtrueになります。m = 143をテストするのと同様に、2、3、5、7、および11で試行除算を行う必要があります（13> 143であるため）。したがって、関数呼び出しisPrime（143、P）の前提条件は、P [0] = 2、P [1] = 3、P [2] = 5、P [3] = 7、およびP [4]=11です。この場合の戻り値は、11が143を除算するため、falseになります。関数isPrime（）には、配列Pをステップスルーし、試行除算を実行するループが含まれている必要があります。このループは、試行除算が成功した場合（falseが返される場合）、またはPの次の素数がmより大きい場合（trueが返される場合）に終了する必要があります。このプロジェクトの関数main（）は、コマンドライン引数nを読み取り、長さnのint配列を割り当て、配列を素数で埋めてから、以下に説明する形式に従って配列の内容をstdoutに出力します。関数main（）のコンテキストでは、この配列をPrimes[]と呼びます。したがって、アレイPrimes[]はこのプロジェクトで2つの役割を果たします。一方では、出力データを収集、保存、および印刷するために使用されます。一方で、これは関数isPrime（）に渡され、新しい整数の素数性をテストします。isPrime（）がtrueを返すときはいつでも、新しく検出された素数は配列Primes[]の適切な位置に配置されます。上で説明したように、mまでの整数mの範囲をテストするために必要な素数は、mがテストされるときに、これらすべての素数（およびそれ以上）が配列Primes []にすでに格納されているため、このプロセスは機能します。もちろん、Primes [0] = 2を手動で初期化してから、関数isPrime（）を使用して素数性のテスト3、4、…に進む必要があります。mがテストされると、これらすべての素数（およびそれ以上）はすでに配列Primes[]に格納されます。もちろん、Primes [0] = 2を手動で初期化してから、関数isPrime（）を使用して素数性のテスト3、4、…に進む必要があります。mがテストされると、これらすべての素数（およびそれ以上）はすでに配列Primes[]に格納されます。もちろん、Primes [0] = 2を手動で初期化してから、関数isPrime（）を使用して素数性のテスト3、4、…に進む必要があります。

以下は、関数main（）で実行される手順の概要です。

• ユーザーが正の整数nとして解釈できるコマンドライン引数を1つだけ指定したことを確認してください。コマンドライン引数が単一の正の整数でない場合、プログラムは以下の例で指定されているように使用法メッセージを出力してから終了します。
• 長さnの配列Primes[]を割り当て、Primes [0]=2を初期化します。
• 後続の素数を検出し、それらをPrimes [1]、Primes [2]、Primes [3]、...、Primes[n-1]として格納するループに入ります。このループには、連続する整数をウォークスルーし、適切な引数を指定して関数isPrime（）を呼び出すことにより、それらの素数性をテストする内部ループが含まれている必要があります。
• 配列Primes[]の内容をstdoutに出力し、10を単一スペースで区切られた行に出力します。つまり、Primes[0]からPrimes[9]は1行目になり、Primes[10]はPrimes[19]は2行目になります。nが10の倍数でない場合、出力の最後の行には10未満の素数が含まれることに注意してください。

Prime.javaと呼ばれるプログラムは、以下のサンプル実行と同じ出力を生成します。（いつものように、％はunixプロンプトを意味します。）

ご覧のとおり、不適切なコマンドライン引数は、多くのUNIXコマンドと同様の使用法メッセージを生成します。（このようなメッセージを表示するには、引数なしでmoreコマンドを実行してみてください。）プログラムには、署名を持つUsage（）という関数が含まれます。

このメッセージをstderrに出力してから、終了します。したがって、プログラムには、main（）、isPrime（）、Usage（）の3つの関数が含まれます。それぞれの前に、名前、操作の簡単な説明、および必要な前提条件（isPrime（）など）を示すコメントブロックを付ける必要があります。Webページの例を参照してください。

試みられた解決策

おそらく任意のビット長の素数を出力する関数 BigInteger.probablePrime(int bitLength, Random rnd) を認識しています。Java で REAL 素数が必要です。許容できるパフォーマンスでこれを行う FOSS ライブラリはありますか? 前もって感謝します！

編集：

私は 1024 と 2048 ビット素数を見ています。

エラトステネスの篩と Python 3.1を使用して素数ジェネレーターを作成しました。このコードは、ideone.comで 0.32 秒で正しく適切に実行され、最大 1,000,000 の素数を生成します。

問題は、1,000,000,000 までの数値を生成しようとすると、メモリが不足することです。

ご想像のとおり、10 億のブール値 ( Python ではそれぞれ1 バイト4 または 8 バイト (コメントを参照)) を割り当てることは実際には不可能なので、bitstringを調べました。各フラグに 1 ビットを使用すると、メモリ効率が大幅に向上すると考えました。ただし、プログラムのパフォーマンスは大幅に低下しました。素数が 1,000,000 までの場合、実行時間は 24 秒です。これはおそらくビット文字列の内部実装によるものです。

上記のコード スニペットのように、3 行をコメントまたはコメント解除して、BitString を使用するように変更した内容を確認できます。

私の質問は、ビット文字列の有無にかかわらず、プログラムを高速化する方法はありますか?

編集: 投稿する前にコードを自分でテストしてください。当然、既存のコードよりも実行速度が遅い回答は受け入れられません。

もう一度編集します。

私のマシンのベンチマークのリストをまとめました。

スフィア オンライン ジャッジ(SPOJ) でいくつかのチャレンジを行っていますが、制限時間内に2 つ目の問題(プライム ジェネレーター) を実行できないようです。次のコードの速度を上げるにはどうすればよいですか?

clojure で素数を計算するための単純なふるい関数を作成しようとしています。効率的なふるい関数の作成に関するこの質問を見たことがありますが、まだその時点ではありません。今、私は非常に単純な (そして遅い) ふるいを書こうとしています。これが私が思いついたものです：

範囲が小さい場合は問題なく動作しますが、範囲が大きい場合はスタック オーバーフローが発生します。

これを使用recurすると、スタックを消費しないループ構造になると思いましたか? 私は何が欠けていますか？