問題タブ [sieve]

私の先生は私にこれをくれました：

n<=10^6;

n 整数の配列 :ai..an(ai<=10^9);

すべての素数を見つけます。

彼はエラトステネスのふるいについて何か言いました、そして私はそれについて読みました、また車輪の因数分解も読みましたが、プログラム（fpc）を1秒で実行する方法をまだ理解できませんでした.?? 私はそれが不可能であることを知っていますが、それでもあなたの意見を知りたい. ホイールの因数分解では、2*3 の円は 25 を素数として扱います。素数として誤って処理されたホイールの最初の数を見つける方法があるかどうか尋ねたいと思います。例: 2*3*5 円 、素数として扱われる最初の合成数を見つける方法?? 助けてください..そして悪い英語でごめんなさい。

空間または時間の複雑さに合わせて最適化されたアルゴリズムを書く練習をしています。素数ふるいでは、少なくとも、見つかったすべての素数のリストを保存する必要があります。見つかった素数の数に比例するデータは、そのようなアルゴリズムが使用するスペースの最小量であるようです。

• この根拠は有効ですか？
• このアルゴリズムのスペースの複雑さはどのように評価されますか?

ウィキペディアからアトキンのふるいについて- 素数の数がこれを超えると、ふるいが O(n^1/2) スペースをどのように使用できるかがわかりません。これが、少なくとも空間が素数の数に比例しなければならないように思われる理由です。可算数と空間の複雑さを混同していませんか?

Atkin のふるいに関するこの論文では、彼らのアルゴリズムは「N までの素数を出力します...ここでの「メモリ」には、プリンターで使用される紙は含まれません。」これはスペースの不公平な計算のようです。

• これがどのように測定されるべきか、実際に客観的に測定されているかを明確にしていただければ幸いです。

次の問題に遭遇しました。1 から N までのすべての素数を取得して出力するクラスがあります。N は、自分で挿入する必要があるパラメーターです。N に 10000 を挿入すると、コードが機能し、2 から N に最も近い素数までのすべての素数が出力されます。

40000 を挿入すると、コードは引き続き機能します。50000 (またはそれ以上) を挿入すると、コードは ArrayOutOfBoundsException を返します。なんで？

これは私が使用するコードです：

そして用途

ポイント「priemgetallen.remove(j*i)」は、エラーが発生する場所です。

誰かが、これがすべての N の約よりも大きい場合に機能しない理由を教えていただければ、本当に感謝しています。40000。

前もって感謝します！

約 1,000,000,000,000 までの小さな素数は、さまざまな情報源から容易に入手できます。Prime Pages (utm.edu)には最初の 5000 万個の素数のリストがあり、primos.mat.brは10^12 まであり、primsieve.orgで利用可能なプログラムのようなプログラムはさらに上位です。

ただし、2 ^ 64 に近い数になると、primes.utm.eduの Primes の 2 の累乗よりわずかに小さいページに記載されている素数は 10 個しかなく、それだけのようです。

そこで見つかった素数性テストは、double に適合しない数の処理を拒否し、他の場所 (他の場所) は拒否に失敗し、ゴミを印刷するだけです。primesieve.org プログラムは、2^64 より少なくとも約 400 億少ない数を扱うことを拒否しています。これは、コーディングの品質に対する信頼を正確に刺激するものではありません。どこでも同じ結果: nada、zilch、niente。

ふるいの歯車と歯車は 2^62 付近できしみ始めます。したがって、信頼できる参照データが不足している/存在しないため、検証が最も困難な場合、実装をテストする必要性が最も高くなります。primesieve.org プログラムは、少なくとも 2^63 程度まで動作する唯一のプログラムのようですが、上記の問題があるため、あまり信頼していません。

では、2^64 に近いふるいが適切に動作することをどのように検証できるのでしょうか? 2^64、2^63 などの 2 のべき乗のすぐ下と上の 100 万 (または 1000 万または 1 億) の素数の信頼できるリストはありますか? それとも、そのようなシーケンスを生成する、または素数または素数のリストを検証できる、信頼できる (信頼できる、検証済みの、多くのことをやり遂げた) プログラムはありますか?

ふるいが検証されると、興味深い範囲の負荷の合計/チェックサムを含む便利なリストを作成するために使用できますが、そのようなリストがないと状況は難しいようです...

PS: 私は、 primsieve.org ターボふるいの上限をUINT64_MAX - 10 * UINT32_MAX、または 0xFFFFFFF600000009と判断しました。つまり、これまでのところ、10 * UINT32_MAX の最も高い素数だけが参照データをまったく持っていないことを意味します...

jQueryプラグイン「tablesorter」を使用して簡単にソートできるテーブルがいくつかあります。最近、ゼブラ ストライプ ウィジェットが含まれていることがわかりました。有効にしましたが、うまく機能しています。

また、既存の自作のテーブル検索機能の代わりに「Sieve」プラグインを追加することにしました。ここで問題が発生しました。検索中または検索後にストライピングがやり直されず、テーブルが不均一で不一致のままになります。

これまでのところ、手動​​で更新する方法を見つけることができませんでした。もしあればどこに置くのかわかりません - sieve .js ファイルで？これら 2 つのプラグインをうまく連携させる方法はありますか?

使用しようとしているコードは次のとおりです。これにより、最大 100 までのすべての素数が生成されます。