問題タブ [sieve]

3 を超えるすべての素数は、次を使用して生成できることがわかっています。

ただし、上記の式から生成されるすべての数値は素数ではありません。

このような状態を解消するために、ふるい法を用いて、上記の式から発生する数の因数となる数を取り除きました。

事実を使用して：

素因数がない数は、素数であると言われます。

1. 上記の式を使用してすべての素数を生成できるためです。
2. 上記の数の倍数をすべて削除できれば、素数だけが残ります。

1000 未満の素数を生成します。

ただし、この方法では正しく素数が生成されます。これは、Sieve でチェックするすべての数値をチェックする必要がないため、はるかに高速に実行されます。

私の質問は、エッジケースが欠けているということですか? これははるかに優れていますが、これを使用している人を見たことがありません。私は何か間違ったことをしていますか？

このアプローチをさらに最適化できますか?

boolean[]an の代わりにaを使用するArrayList方がはるかに高速です。

私はアトキンのふるいを実装しましたが、100,000,000 に近い素数までうまく機能します。それを超えると、メモリの問題のために故障します。

アルゴリズムでは、メモリ ベースのアレイをハード ドライブ ベースのアレイに置き換えたいと考えています。Python の "wb" ファイル関数と Seek 関数がうまくいくかもしれません。新しい車輪の発明に取り掛かる前に、誰かアドバイスをいただけますか? 最初に 2 つの問題が発生します。

1. アトキンのふるいを「チャンク」してメモリ内のセグメントで作業する方法はありますか?
2. アクティビティを一時停止して後で戻ってくる方法はありますか?メモリ変数をシリアル化して復元できることを示唆しています。

なぜ私はこれをしているのですか？娯楽を求め、麺を動かし続けるために年老いたオヤジ。

以下の [Python 3.4] のプログラムは、単純なエラトステネスふるいです。

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] を生成します。わかった。excl() をインライン化する行のコメントを外し、呼び出しをコメントにすると、[2, 3, 4, 5, 6, 7, 8, 9, 10, 11] が得られます。なんで？

それを反復するループ内でシーケンスを変更するときに予想されるトラブルに関連していますか?

ヒントをありがとう。

素数であるすべての偽の値を出力するように設定しますが、25 個のうち出力します。3, 5, 7, 8, 9, 11, 13, 14, 15, 17, 19, 20, 21, 23, 24, なぜそれらのいくつかがすり抜けるのかわかりません. 問題への洞察は素晴らしいでしょう。

または、単に書き込み方向に向けてください。8 などの非素数が出力されるのはなぜですか?

問題：見つける

nの範囲: 1<= n <=

主な課題は、大きくなる可能性のあるクエリ (Q) の処理です。1 <= Q <=

これまでに使用した方法：

強引な

複雑さ :

でのクエリの前処理と処理

最初に、すべての N のオイラー totient 関数の値を保持するテーブルを作成します。これは O(N) で実行できます。

各クエリに対して N を因数分解d*phi[d]し、結果に追加します。

これには O(sqrt(N)) が必要です。

複雑さ : O(Q*sqrt(N))

O(1) でクエリを処理する

上で説明したふるい法に、必要な答えを O(NLogN) で計算する部分を追加します。

残念ながら、これは指定された制約と制限時間 (1 秒) でタイムアウトになります。

これには、 N の素因数分解に関する巧妙なアイデアが含まれていると思います。上記で作成した lp(lowest prime) テーブルを使用して O(LogN) の数値を素因数分解できますが、因数分解を使用して答えに到達する方法がわかりません。

次のプライムシーブでは：

x | x <- xsとはどういうx `mod` p > 0意味ですか?

これが私の素数検索アルゴリズムです-制限が173を超えて設定されるまではうまく機能し（そして非常に高速に）、その後スローを開始します

制限が 174 以上になるまで完全に正常に動作する理由がわかりません。これが私のコードです。

totients のリスト用にふるいベースのジェネレーターを作成し、合計を 1000000 にしたいと考えています。

totientSum n40000を超える計算をn行うと、ghci は評価に時間がかかり、膨大な量のメモリを消費し始めます。実行可能ファイルへのコンパイルは役に立ちません。これは、Haskell が遅延評価を処理する方法と関係があると思います。

上記の関数のメモリ消費を改善するために厳密性を選択的に適用して、最大 1000000 までの合計を計算できるかどうかを知りたいです。また、リストを使用してこれを行うより良い方法があるかどうかも知りたいです。ランダム アクセス データ構造を使用する必要がある場合。全合計を計算するためのより高速なアルゴリズムを知っている場合は、参考文献を共有してください。

の定義がapplyEvery違うのではないかと思い、以下の他の実装も試してみましたが、どちらも上記の定義よりも多くのメモリを消費しているようでした。