サンダラムの篩

サンダラムの篩（サンダラムのふるい、テンプレート:Lang-en-short）は、指定された整数以下の全ての素数を発見するための単純な決定的アルゴリズムである。これは1934年にサスヤマンガラム（Sathyamangalam ）の生徒であるSP Sundaramによって発見された。

アルゴリズム

サンダラムの篩： 202以下の素数を発見するアルゴリズムのステップ（最適化されていない）

1から n までの整数のリストから開始する。このリストから、次の条件を満たす i + j + 2ij の形になる全ての数字を削除する。

• $i,j\in \mathbb{N},1\le i\le j$
• $i+j+2ij\le n$

残った数字を2倍し1を足すと、2n + 2より小さい素数のうち、2を除いたリストができる。

サンダラムの篩ではエラトステネスの篩と同様に合成数をふるい落としていくが、サンダラムの篩では2の倍数は考慮されていない。2の倍数を消す作業は、最後の2倍し、1を足す作業で行われる。 エラトステネスの方法が素数$2i+1$の異なる$k$個の倍数を除外するとき、サンダラムの方法では$1\le j\le \lfloor k/2\rfloor$を満たす $i+j(2i+1)$を除外する。

正当性

最終的な2倍し、1をたされた整数のリストは、3から2n+1までの奇数が含まれている。私たちは、リストから除外された奇数は真に合成数であることを示さなければならない。

奇数の整数は、それが2(i + j + 2ij) + 1という形で表せ、かつそのときに限り最終的なリストから除外されている。このとき、

$\begin{array}{cc}2(i+j+2ij)+1& =2i+2j+4ij+1\\ & =(2i+1)(2j+1).\end{array}$

よって、奇数はそれが(2i + 1)(2j + 1)と因数分解される場合、つまり非自明な奇数の因数を持つ場合かつそのときに限り最終的なリストから除外される。したがって、最終的なリストは$2n+2$以下の奇素数だけを含む。

関連項目

• 篩法
• エラトステネスの篩
• アトキンの篩 - より現代的で高速なアルゴリズム

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• A new "sieve" for primes, an excerpt from テンプレート:Cite book (translation of Russian book テンプレート:Cite book)
• テンプレート:Cite journal
• テンプレート:Cite conference
• テンプレート:Cite journal