プログラミングの背景で「エラトステネスの篩」を公開しました。
プログラミングの背景で「エラトステネスの篩」を公開しました。
http://www.tbasic.org/reference/numbertheory/202006Eratosthenes.pdf
旧ホームページでの「エラトステネスの篩」の更新ということですが，今回は大幅に
加筆しています。
書き始めた当初は，もっとあっさりとするつもりでしたが，書いてくるうちに，色々疑問もでて，考えるとともに，色々な文献を調べたりしました。そのうちに，いわゆるエラトステネスの篩だけでなく，その改良版についての全体的説明を纏めたいと思うようになりました。その結果，全体で，94ページにもなりました。
内容は，実際に見てもらうと早いですが，以下の通りです。
・基本篩（これが元々のエラトステネスの篩です。）
・改良篩
・車輪篩
・リスト篩
・既約篩
そして，
・区分法（これは篩法ではなく，篩を分割して実行する技法です。）
等について，かなり詳しく説明しました。恐らくこれほど詳しい内容は，日本語の文献では見かけません。エラトステネスの篩について興味のある人に参考になれば，と思っています。
付録として，ここで説明した方法を使って，大きな素数表の作成にチャレンジしました。勿論，tbasicでそれを行うのは無理ですから，ここでは，C#を使いました。その結果，
・既約篩法を使って，一度の篩で，10^10までの素数表を作成することができました。
更に，区分法を併用することで，
・10^13までの素数表を篩うことができました。
（10^13までの素数表を作る試みはネット上でもいくつか見られますので，これ自体は全く新しいというものではありません。ただあまり技巧的ではない，標準的なプログラミングで実行したという意義はあるかもしれません。）
私自身，書いていて勉強にもなり，楽しむこともできました。私のコンピュータ環境（エントリー的なデスクトップ機）ではこれ以上の計算は無理なので，一応ここまでとして，公開しました。