問題タブ [primes]

私の学校のコンピューター サイエンス関連の新聞 ( readmeと呼ばれる、ノルウェー語で、19 ページ) では、次の問題に対して可能な限り短い Java コードを作成するための楽しいコンテストが行​​われました。

引数として整数 (文字列配列の最初のエントリの文字列として。Java のメイン メソッドは文字列配列のみを受け取るため) を引数として取り、最初にこの数値より下の素数であるすべての数値を書き出し、次にすべての数値を書き出します。は素数ではありません。最短のコードが勝ちます!

答えとして、競争に勝った最短の Java コードを投稿します。スタック オーバーフロー コミュニティはもっと短いコードを作成できるのではないでしょうか ノルウェー語を知っていれば、それを行っていればシャンパン 1 本を獲得できたはずですが、残念ながらコンテストの最終提出日は終了しています。

この問題をどのように解決したでしょうか。

MLでは、数の素数の約数を取得したいと思います。どうすればこれができますか、私は初心者です。

私はC＃が初めてです。そして、ユーザーがテキストボックスに整数を入力すると、リストボックスに素数を表示するようなプログラムを作成したいと思います。(つまり、10 と書くと、0 から 10 までの素数、または 0 から 20 までの 20 などの素数が表示されます)。

プログラミングを行う前に、まず何を考慮する必要がありますか? インターネットには多くの例があることは知っていますが、まず何が必要か知りたいですか?

ヒントをありがとう;-)

=== ありがとうございます。では、最初にコンソール アプリケーションで実行する方がよいということですか? コンソール アプリケーションを使用して非常に単純な "For ループ" の例を作成しましたが、Windows フォーム アプリケーションで実行しようとすると、実装方法がわかりません。残念ながら、コンソールで例を実行し続けると、Windows フォーム アプリで実行するのが難しくなります。どう思いますか？

====== こんにちは。

コードに関するフィードバックが必要です。

そこで、私は素数を遅延生成する方法に取り組んでいました。これらの 3 つの定義を思いつきました。これらはすべて同等の方法で機能します。つまり、新しい整数のそれぞれが先行するすべての素数の因数を持っているかどうかをチェックするだけです。

したがって、すべての整数の再計算を回避 し（これまでに見つけた素数の数の順序で作業が必要だと思いますprimes2）、新しいプライム。primes1f_ = f (const True)

非科学的なテスト (ghci で実行) から見ると、よりも高速に実行take 1000されるようです。primes3primes2

このことから教訓を得て、関数を配列の操作として表現できる場合、効率のために後者の方法で実装する必要があると仮定する必要がありますか、それともここで何か他のことが起こっているのでしょうか?

C++ でビット操作を介して素数を見つけるにはどうすればよいですか?

数を一連のに変換する単純な暗号があり ます。 （ ）

数値（0 .. 2147483647）をこの表現に暗号化するには、次のものが必要です。

• 素因数分解
• 与えられたp（pはPrime）に対して、pの順序シーケンス（つまり、 PrimeOrd（2） == 0、PrimeOrd（227） == 49）

いくつかの例

問題のソースコード

問題は、プロシージャPrimeOrdのスローネスです。素数の素数の順序を見つけるためのより速い解決策を知っていますか？

見出し

素数の順序をすばやく見つける方法を知っている場合は、何か提案してください。:-)

ありがとうございました。

PS 2,147,483,648未満の最大の素数は2,147,483,647で、105,097,565番目の素数です。2^31より大きい数を期待する必要はありません。

私はClojure でProject Eulerの問題を解決することに取り組んでいますが、すでに数回素数の生成に遭遇しています。私の問題は、時間がかかりすぎることです。Clojure-y の方法でこれを行う効率的な方法を誰かが見つけるのを手伝ってくれることを望んでいました。

私がこぶしでこれをやったとき、私は力ずくでそれをやりました。それは簡単にできました。しかし、Xeon 2.33GHz で 10001 の素数を計算するには、この方法で 2 分かかりました。アルゴリズムは次のとおりです。

next-prime-slow を、いくつかの追加ルール (6n +/- 1 プロパティなど) を考慮した新しいルーチンに置き換えることで、約 70 秒まで高速化することができました。

次に純粋なClojureでエラトステネスのふるいを作ってみました。すべてのバグを取り除いたとは思いませんが、単純に遅すぎたのであきらめました (上記よりもさらに悪いと思います)。

これは悪いです。また、数値 150000 が小さい場合、スタック オーバーフローが発生します。これは、recur を使用しているにもかかわらずです。それは私のせいかもしれません。

次に、Java ArrayList で Java メソッドを使用してふるいを試しました。それにはかなりの時間とメモリが必要でした。

私の最新の試みは、Clojure ハッシュマップを使用したふるいです。ふるいにすべての数値を挿入してから、素数ではない数値を分解します。最後に、見つかった素数であるキー リストを取得します。10000 個の素数を見つけるのに約 10 ～ 12 秒かかります。まだ完全にデバッグされているかどうかはわかりません。私は Lispy になろうとしているので、これも再帰的です (recur と loop を使用)。

したがって、この種の問題では、問題 10 (2000000 未満のすべての素数を合計する) が私を殺しています。私の最速のコードは正しい答えを思いつきましたが、それを行うのに 105 秒かかり、かなりの量のメモリが必要でした (私はそれに 512 MB を与えたので、大騒ぎする必要はありませんでした)。私の他のアルゴリズムは時間がかかりすぎて、いつも最初にそれらを止めてしまいました。

ふるいを使用して、Java または C で非常に高速に、多くのメモリを使用せずに多くの素数を計算できます。問題の原因となっている Clojure/Lisp スタイルの何かが欠けているに違いないことはわかっています。

私が本当に間違っていることはありますか？Clojure は大規模なシーケンスでちょっと遅いですか? プロジェクトの Euler に関する議論を読んでいると、人々は他の Lisp で最初の 10000 個の素数を 100 ミリ秒未満で計算しました。JVM によって速度が低下する可能性があり、Clojure が比較的新しいことはわかっていますが、100 倍の違いは期待できません。

Clojure で素数をすばやく計算する方法を教えてもらえますか?

（C＃、素数ジェネレーター）ここに友人と私が突っついていましたいくつかのコードがあります：

私のドーキーなAMDx641800+（デュアルコア）では、34546.875msで10億未満のすべての素数に対して。問題は、ビット配列により多くを格納しているようです。20億を超えてクランキングしようとすることは、ビット配列が格納したい以上のことです。それを回避する方法について何かアイデアはありますか？

私は現在プロジェクトを行っており、素数を計算するための効率的な方法が必要です。私はエラトステネスのふるいを使ったことがありますが、いろいろと調べてみたところ、アトキンのふるいの方が効率的であることがわかりました。この方法の説明 (私は理解できました!) を見つけるのが難しいことがわかりました。それはどのように機能しますか？サンプル コード (できれば C または python) はすばらしいでしょう。

編集:ご協力ありがとうございます。私がまだ理解していないのは、疑似コードで x 変数と y 変数が参照しているものだけです。誰かが私のためにこれに光を当てることができますか?