サンダラムの篩
最終的な2倍し、1をたされた整数のリストは、3から2n+1までの奇数が含まれている。私たちは、リストから除外された奇数は真に合成数であることを示さなければならない。
奇数の整数は、それが2(i + j + 2ij) + 1という形で表せ、かつそのときに限り最終的なリストから除外されている。このとき、
2 ( i + j + 2 i j ) + 1 = 2 i + 2 j + 4 i j + 1 = ( 2 i + 1 ) ( 2 j + 1 ) . {\displaystyle {\begin{aligned}2(i+j+2ij)+1&=2i+2j+4ij+1\\&=(2i+1)(2j+1).\end{aligned}}}
よって、奇数はそれが(2i + 1)(2j + 1)と因数分解される場合、つまり非自明な奇数の因数を持つ場合かつそのときに限り最終的なリストから除外される。したがって、最終的なリストは 2 n + 2 {\displaystyle 2n+2} 以下の奇素数だけを含む。
1から n までの整数のリストから開始する。このリストから、次の条件を満たす i + j + 2ij の形になる全ての数字を削除する。
i , j ∈ N , 1 ≤ i ≤ j {\displaystyle i,j\in \mathbb {N} ,\ 1\leq i\leq j}
i + j + 2 i j ≤ n {\displaystyle i+j+2ij\leq n}
残った数字を2倍し1を足すと、2n + 2より小さい素数のうち、2を除いたリストができる。
サンダラムの篩ではエラトステネスの篩と同様に合成数をふるい落としていくが、サンダラムの篩では2の倍数は考慮されていない。2の倍数を消す作業は、最後の2倍し、1を足す作業で行われる。 エラトステネスの方法が素数 2 i + 1 {\displaystyle 2i+1} の異なる k {\displaystyle k} 個の倍数を除外するとき、サンダラムの方法では 1 ≤ j ≤ ⌊ k / 2 ⌋ {\displaystyle 1\leq j\leq \lfloor k/2\rfloor } を満たす i + j ( 2 i + 1 ) {\displaystyle i+j(2i+1)} を除外する。