問題タブ [primes]

これは宿題ではありません。ただ興味があるだけです。

INFINITE がここでのキーワードです。

として使いたいfor p in primes()。これはHaskellの組み込み関数だと思います。

したがって、答えは「ふるいをするだけ」ほど単純ではありません。

まず、素数が連続して何回消費されるかわかりません。一度に 100 個を合成できるとします。素数公式の頻度だけでなく、同じふるいアプローチを使用しますか?

私は非並行アプローチを好みます。

読んでくれて (そして書いてくれてありがとう ;) )!

私はSchemeが初めてです。PLTスキームを使用して、ラビンミラーアルゴリズムの確率的バリアントを試して実装しました。私はそれが確率的であることを知っていますが、ほとんどの場合、間違った結果を得ています。私は C を使用して同じことを実装しましたが、うまくいきました (試行に失敗したことはありません)。デバッグ中に期待どおりの出力が得られますが、実行すると、ほとんどの場合、間違った結果が返されます。Wikipediaのアルゴリズムを使用しました。

また、Scheme で正しい方法でプログラミングしていますか? （私が使用するループ部分の抜け出しについてはよくわかりませんcall/cc。あるサイトで見つけて以来、それを使用しています。）

前もって感謝します。

ビット演算のみを使用して2の累乗から指数を抽出する簡単な方法はありますか？

編集：質問はもともとビット演算に関するものでしたが、 「 PythonでY = 2 Xの場合にXを見つける最も速い方法は何ですか？」**

私は現在、フォームの偶数Nを減らすルーチン（ Rabin-Miller素数性テスト）を最適化しようとしています。私は次の方法で部品を入手できます：2**s * d2**s

しかし、ビット演算で「 s 」だけを抽出する方法が見つかりません。私が現在あまり満足せずにテストしている回避策（それらはすべてかなり遅いです）は次のとおりです。

• 対数関数を使用する
• 2 **のバイナリ表現を操作する（つまり、末尾のゼロを数える）
• 結果が1になるまで2で除算をループします

私はPythonを使用していますが、この質問に対する答えは言語に依存しないはずです。

「 n番目の素数を計算する」ための最短のCコードは何ですか?

意味のある文字の点で最短。つまり、セミコロン、空白以外の文字、キーワード、カンマの数。

入力：

改行で区切られた、標準入力からの整数n 。入力は EOF で終了します。

出力：

入力nの直後に、n番目の素数を改行で区切って標準出力に出力します。

(素数は < 10,000、つまりn < 1,230 であると想定できます。)

テストケース:

私の試み：

この問題では、可読性は問題ではありません。時間とメモリの点でコストがかかるが、制約を満たすコードは、ここではより良いと見なされます。

アルゴリズムの提案が必要です。

与えられた数 N に対して、次のように、それを構成するすべての素数を見つける必要があります。

さらに私を助けたい場合は、C++ でアルゴを書くことができます。

ありがとう。

数が素数かどうかを判断するプログラムを書こうとしています。私はそれをエラトステネスのふるいに基づいています。とにかく、私のプログラムは小さい数（15485863は動作します）で動作しますが、大きい数（例：17485863）を使用すると、セグメンテーション違反が発生します。unsigned long longを使用していますが、最大値を超えていないと思います。何を間違えたのかわかりません。よろしくお願いします！

私は大学の学生で、大きな素数を見つける必要がある課題があります。私は教授から次の「単純な」アルゴリズムを与えられ、2つの可能性のある素数を見つけました。

1. 1 < a < p の場合、ランダムな a と p を生成します
2. gcd(a,p) が = 1 であることを確認します -- これは、カーマイケル数を削除することを想定しています Edit(meant equal to 1)
3. x ^ (p-1) % p = 1 の場合、「モジュラー累乗」を実行します。ここで、x はゼロから始まり、p と a の両方で p-1 まで増加します

3番目のステップの例。

p = 5 とします。

1^4 %5 = 1

2^4 %5 = 1

3^4 %5 = 1

4^4 %5 = 1

これは 5 が素数であることを示しています。

この課題を通して、素数の計算は冗談ではないことに気づきました。上記のアルゴリズムで見られる問題は、大きな数を推測して剰余累乗でテストしている場合、大きな数を大きな数に上げようとしている可能性があることです。これは私の心に疑問を投げかけます。私は決定論的有限オートマトンとエラトステネスのふるいも調べました。指定されたアルゴリズムを改善するか、何らかの支援を提供するための提案はありますか? ありがとうございました。

与えられた数が素数であるかどうかをチェックする最速の方法を見つけようとしています（Javaで）。以下は私が思いついたいくつかの素数判定方法です。2番目の実装（isPrime2）よりも良い方法はありますか？

私のSieveofAtkinの実装では、限界近くの素数または限界近くのコンポジットを見落としています。一部の制限は機能し、他の制限は機能しません。私は何が悪いのか完全に混乱しています。

たとえば、1000の制限まで素数を生成すると、アトキンのふるいは素数997を見逃しますが、複合965を含みます。しかし5000の制限まで生成すると、返されるリストは完全に正しいです。

数が素数か合成数かを判断するプログラムを作成しようとしています。私はここまで来ました。それが機能するように、何かアイデアを教えていただけますか？ただし、すべての素数は になりますが、コンポジットには r>0 と r==0 の両方の値があるため、それらは常に素数として分類されます。どうすればこれを修正できますか?