エラトステネスの篩（ふるい）とは

エラトステネスの篩は、ある特定の整数以下の全ての素数を効率的に見つけるためのアルゴリズムです。古代ギリシアのエラトステネスが考案したことからこの名前がついています。

アルゴリズムの仕組み

1. 初期化:

   • 2から調べたい最大の整数Nまでの全ての数を素数だと仮定します。
   • 通常、配列を用いて、各数が素数か合成数かを管理します。

2. 素数の特定と合成数の排除:

   • まだ処理されていない数の中で最小の数を素数として確定します。
   • その素数の倍数を全て合成数としてマークします。
   • 未処理の数のうち、次の最小の数を素数として確定し、同様の処理を繰り返します。

3. 終了条件:

   • 調べたい最大の整数Nを超えたら終了です。

例: 30以下の素数を求める場合

1. 2から30までの数を素数と仮定します。
2. 2は素数なので、2の倍数(4, 6, 8, ...)を合成数とマークします。
3. 次に、未処理の数のうち最小の3が素数なので、3の倍数(6, 9, 12, ...)を合成数とマークします。
4. 以下、同様にして、5, 7, 11, 13, 17, 19, 23, 29が素数と判明します。

具体的な実装例 (Python)

Python

def eratosthenes(n):
    """エラトステネスの篩

    Args:
        n: 調べる最大の整数

    Returns:
        list: n以下の素数のリスト
    """

    # 2からnまでの数を素数と仮定する配列
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0と1は素数ではない

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    return [i for i, prime in enumerate(is_prime) if prime]

# 30以下の素数を求める
primes = eratosthenes(30)
print(primes)

エラトステネスの篩の利点

• シンプルで分かりやすいアルゴリズム:
  • 基本的な概念は非常にシンプルで、実装も容易です。
• 効率性:
  • 素数の分布に関する性質を利用することで、多くの合成数を一度に排除できます。
  • 特に、小さい素数の倍数を先に処理することで、計算量を削減できます。

応用

エラトステネスの篩は、数論の様々な問題を解く際に利用されます。例えば、

• 素因数分解: 与えられた数を素因数に分解する際に、エラトステネスの篩で事前に素数のリストを作っておくと便利です。
• その他の数論の問題: 合成数の判定、フィボナッチ数列の素数判定など、様々な問題に適用できます。

エラトステネスの篩は、そのシンプルさと効率性から、多くのプログラミング言語で実装されており、アルゴリズム学習の入門としても最適です。

さらに詳しく知りたい方へ

• 計算量: エラトステネスの篩の計算量はO(n log log n)であり、ほぼ線形時間とみなせるほど効率的です。
• 最適化: エラトステンスの篩には、さらに効率化するための様々な手法が存在します。
• 他の素数判定アルゴリズム: ミラー・ラビン素数判定法など、より大規模な数に対する素数判定に適したアルゴリズムもあります。

これらの詳細については、より専門的な書籍や論文を参照してください。

何か他に知りたいことがあれば、お気軽にご質問ください。