エラトステネスの篩い @ 素因数分解 @ IDM

最終更新日:2003.05.31 目次 紹介 アルゴリズムの基本 Rubyによる実装 改良1:偶数を省く 改良2:配列の分割 実装 関連資料 変更履歴 紹介 最も古典的な素数表作成アルゴリズムとして、エラトステネスの篩い(Eratosthenes's sieve)があります。 今ではより効率的な代替アルゴリズムもありますが、次に挙げる理由から、ここではエラトステネスの篩いを説明します。 実装が簡単である。1000以下の素数を列挙する程度なら、計算機を用いなくても紙と鉛筆で実行できるほどである。 2の30乗以下の素数を列挙する程度であれば、十分な速度が得られる。 篩い系素因数分解アルゴリズムの基礎となっている。 「より効率的な代替アルゴリズム」を私が理解していない。 一番上に戻る アルゴリズムの基本 求める素数の上限値をMとします。初めに、2からMまでの整数を全て書きます。 計算機に於いては

[side_tana]

後で読む

[elim]

だけじゃないけど