サンダラムの篩

サンダラムの篩（サンダラムのふるい、英: Sieve of Sundaram）は、指定された整数以下の全ての素数を発見するための単純な決定的アルゴリズムである。これは1934年にサスヤマンガラム（Sathyamangalam[1][2] ）の生徒であるSP Sundaramによって発見された。

アルゴリズム

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

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)} を除外する。

正当性

最終的な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. ^ V. Ramaswami Aiyar (1934). “Sundaram's Sieve for Prime Numbers”. The Mathematics Student 2 (2): 73. ISSN 0025-5742. 
  2. ^ G. (1941). “Curiosa 81. A New Sieve for Prime Numbers”. Scripta Mathematica 8 (3): 164. 

参考文献

  • Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from Oxford University Press, 1966). pp. 98–100, 158. ISBN 0-486-25778-9. https://books.google.com/books?isbn=0-486-25778-9 
  • Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. pp. 75. ISBN 0-394-70923-3 
  • A new "sieve" for primes, an excerpt from Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. pp. 200  (translation of Russian book Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ. http://ilib.mccme.ru/djvu/klassik/smekalka.htm )
  • Movshovitz-Hadar, N. (1988). “Stimulating Presentations of Theorems Followed by Responsive Proofs”. For the Learning of Mathematics 8 (2): 12–19. 
  • Ferrando, Elisabetta (2005). "Abductive processes in conjecturing and proving" (PDF). Ph.D. theses. Purdue University. pp. 70–72.
  • Baxter, Andrew. “Sundaram’s Sieve”. Topics from the History of Cryptography (MU Department of Mathematics). http://banach.millersville.edu/~bob/math478/History/Sundaram.html.