投稿者 スレッド: 「エラトステネスの篩」を公開しました。  (Read 694 times)

takeuchi

  • 管理人
  • *****
  • 投稿: 85
「エラトステネスの篩」を公開しました。
« 投稿日:: 2020年 6月 11日 , 午後 09:40:06 »
 プログラミングの背景で「エラトステネスの篩」を公開しました。

http://www.tbasic.org/reference/numbertheory/202006Eratosthenes.pdf

 旧ホームページでの「エラトステネスの篩」の更新ということですが,今回は大幅に
加筆しています。
 書き始めた当初は,もっとあっさりとするつもりでしたが,書いてくるうちに
色々疑問もでて,考えるとともに,色々な文献を調べたりしました。そのうちに,
いわゆるエラトステネスの篩だけでなく,その改良版についての全体的説明を纏めたい
と思うようになりました。その結果,全体で,94ページにもなりました。

 内容は,実際に見てもらうと早いですが,以下の通りです。
・基本篩(これが元々のエラトステネスの篩です。)
・改良篩
・車輪篩
・リスト篩
・既約篩
そして,
・区分法(これは篩法ではなく,篩を分割して実行する技法です。)
等について,かなり詳しく説明しました。恐らくこれほど詳しい内容は,日本語の文献では
見かけません。エラトステネスの篩について興味のある人に参考になれば,と思っています。

 付録として,ここで説明した方法を使って,大きな素数表の作成にチャレンジしました。
勿論,tbasicでそれを行うのは無理ですから,ここでは,C#を使いました。その結果,

・既約篩法を使って,一度の篩で,10^10までの素数表を作成することができました。
更に,区分法を併用することで,
・10^13までの素数表を篩うことができました。
(10^13までの素数表を作る試みはネット上でもいくつか見られますので,これ自体は
全く新しいというものではありません。ただあまり技巧的ではない,標準的なプログラミング
で実行したという意義はあるかもしれません。)

 私自身,書いていて勉強にもなり,楽しむこともできました。私のコンピュータ環境
(エントリー的なデスクトップ機)ではこれ以上の計算は無理なので,
一応ここまでとして,公開しました。