今日は豪華二本立てです。
以前、メモリをめちゃくちゃ確保するプログラムを作ったのですが、今回は素数を計算するプログラムを作りました。
普通に素数を計算するプログラムを書くと、大体は配列に順番に値を書き込んでいくと思いますが、それだとそのうち配列が一杯になって一定以上計算できなくなります。
配列は静的領域になるのでそこまで大きな領域を確保できません。
そこで、動的にメモリを確保しながら配列みたいなことをすれば大きな素数でも計算できるのではないかというのが今回のプログラムの肝になります。
プログラムは以下のリポジトリからダウンロードできます。Windows 64bit版についてはビルドしたものをReleaseに置いてあるのでそれをダウンロードしてもOKです。
実行したら、好きな番目の素数を入れてください。小さいものであればすぐに、大きいものであればそれなりに時間が経ってから結果が出ます。
仕組みはとても単純で、素数となる値と次の構造体のポインタを記憶する構造体をリスト状につなげているだけです。
ポイントは再帰関数を使わないことです。詳しくは前回の記事をご覧いただければと思います。
最近のコンピュータはメモリがたくさんあるので100万個目とかでもメモリリークしないと思います。どちらかといえば計算アルゴリズムがエラトステネスの篩なので計算にすこぶる時間がかかるぐらいだと思います。
