サンダラムの篩のソースを表示

'''サンダラムの篩'''（サンダラムのふるい、{{lang-en-short|''Sieve of Sundaram''}}）は、指定された[[整数]]以下の全ての[[素数]]を発見するための単純な[[決定的アルゴリズム]]である。これは1934年にサスヤマンガラム（[[Sathyamangalam]]<ref>{{cite journal |author=V. Ramaswami Aiyar |title=Sundaram's Sieve for Prime Numbers |journal=The Mathematics Student |volume=2 |year=1934 |pages=73 |issn=0025-5742 |issue=2}}</ref><ref>{{cite journal |author=G.|title=Curiosa 81. A New Sieve for Prime Numbers |journal=[[Scripta Mathematica]] |volume=8 |year=1941 |pages=164 |issue=3}}</ref>
）の生徒であるSP Sundaramによって発見された。

==アルゴリズム==
[[File:Sieve of Sundaram Animated.gif|right|frame|サンダラムの篩： 202以下の素数を発見するアルゴリズムのステップ（最適化されていない）]]
1から ''n'' までの整数のリストから開始する。このリストから、次の条件を満たす ''i'' + ''j'' + 2''ij'' の形になる全ての数字を削除する。
*<math>i,j\in\mathbb{N},\ 1 \le i \le j</math>
*<math>i + j + 2ij \le n</math>

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

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

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

奇数の整数は、それが2(''i'' + ''j'' + 2''ij'') + 1という形で表せ、かつそのときに限り最終的なリストから除外されている。このとき、
: <math> \begin{align}
2(i + j + 2ij) + 1
 &= 2i + 2j + 4ij + 1 \\
 &= (2i + 1)(2j + 1).
 \end{align}</math>

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


==関連項目==
*[[篩法]]
*[[エラトステネスの篩]]
*[[アトキンの篩]] - より現代的で高速なアルゴリズム

==脚注==
{{脚注ヘルプ}}{{reflist}}

== 参考文献 ==
* {{cite book |last=Ogilvy |first=C. Stanley | authorlink = C. Stanley Ogilvy |author2=John T. Anderson  |title= Excursions in Number Theory |publisher=[[Dover Publications]], 1988 (reprint from [[Oxford University Press]], 1966) |isbn=0-486-25778-9 |url=https://books.google.com/books?isbn=0-486-25778-9 |pages=98–100, 158 |year=1988}}
* {{cite book |last=Honsberger |first=Ross |title=Ingenuity in Mathematics |publisher=[[Mathematical Association of America]] |series=New Mathematical Library #23 |year=1970 |isbn=0-394-70923-3 |pages=75}}
* [http://www.primzahlsuche.de/intro.html#sieve2 A new "sieve" for primes], an excerpt from {{cite book |last=Kordemski |first=Boris A. |authorlink=Boris Kordemsky |title=Köpfchen, Köpfchen! Mathematik zur Unterhaltung|publisher=Urania Verlag| year=1974 |series=MSB Nr. 78 | pages=200}} (translation of Russian book {{cite book |last=Кордемский |first=Борис Анастасьевич |title=Математическая смекалка |publisher=М.: ГИФМЛ |year=1958 |url=http://ilib.mccme.ru/djvu/klassik/smekalka.htm}})
* {{cite journal |last=Movshovitz-Hadar |first=N. |year=1988 |title=Stimulating Presentations of Theorems Followed by Responsive Proofs |journal=For the Learning of Mathematics |volume=8 |issue=2 |pages=12–19}}
* {{cite conference |last=Ferrando |first=Elisabetta |title=Abductive processes in conjecturing and proving |book-title=Ph.D. theses |publisher=Purdue University |year=2005 |pages=70–72 |url=http://proxy.sv.inge.unige.it/SMA/Sv/AbPCP.pdf}}
* {{cite journal |last=Baxter |first=Andrew |title=Sundaram’s Sieve |journal=[http://banach.millersville.edu/~bob/math478/History/ Topics from the History of Cryptography] |publisher=MU Department of Mathematics |url=http://banach.millersville.edu/~bob/math478/History/Sundaram.html}}

{{デフォルトソート:さんたらむのふるい}}
[[Category:数論]]
[[Category:素数判定]]
[[Category:数学に関する記事]]