エラトステネスの篩

久々の更新です。

http://dev.team-lab.com/?itemid=207
こんな記事を見つけたので、挑戦してみました。
1000万番目の素数を出来るだけ早く出力する課題です。

素数を求める方法として有名なのが、エラトステネスの篩です。
ある範囲の自然数の数列を用意して、２の倍数のものを取り除く、次は３の倍数を、次は５、というようにして、合成数（約数が１と自身の値以外に存在する数）を取り除いていく方法です。
Wikipediaに分かりやすいgifアニメがあったので、イメージがつかみにくい人は、そちらを見ると良いかと思います。

エラトステネスの篩は、求めたい範囲が広くなれば広くなるほど、計算量がどんどん増えていきます。
今回は 10^7番目の素数を求めたいので、結構な範囲になります。（1.8*10^8ぐらい）


とりあえずC++で実装してみました。
char配列を2億個ぐらい用意して、要素の添字を、その要素の値としました。
あとは単純にforループを回して、2の倍数、3の倍数の要素にフラグを立てていくだけのプログラムでテスト。

そこそこ動くけど、何十秒もかかってる。
さっきの記事をもう一回見たところ、１位の人は1.4秒で出力してる！！！

改良の余地はたくさんあるらしいので、いろいろ試してみました。
最終的なコードがこれ。
https://gist.github.com/nekosan/a956c2794796750280ec

何を改良したかはコードから察して欲しい。（気力がないし、ぐぐると結構いろいろ出てきました）
配列からあらかじめ２の倍数のものを抜いたり、ループの回し方を変えたりしました。

最終的には、出力時間を0.9秒まで縮めることができました。（CPUはIntel Core i7 2.2GHz）
もうちょっと改良すれば縮められそうですが、疲れたので一区切りつけました。


単純に興味があってコードを書き始めましたが、結構勉強になりました。
演算子の処理時間とかを考えないといけないコードを最近書いてなかったので、いい復習になった気がします。

次もプログラミング関連の投稿になると思います。
そろそろ自分のHPぐらい持ってみたいものです。VPSとか借りようかな。

あけましておめでとうございました

あけましておめでとうございました。
今年も、nekolabをよろしくお願いします。

２ヶ月ぶりの更新ですね。さぼってました。

ネタがないです。
何か作ったらまた更新しますね。

BrainWarsが楽しい

最近、技術ネタが無いので、趣向を変えてみました。


Android/iOSでリリースされている、BrainWarsというアプリを入れてみました。
「リアルタイム対戦型脳トレ」です。


神経衰弱、四則演算などの、いわゆる脳トレアプリがいくつか入っており、その成績を他のプレイヤーと競います。

このゲームの目玉は、なんと言ってもリアルタイムネット対戦です。
世界中の人と競い合いながら、脳トレをすることが出来ます。

1回の対戦は5分ぐらいで終わるので、ちょっと暇になった時にぴったりのアプリです。


また、各脳トレの成績から、能力チャートが作られます。
ある程度、対戦時の参考になったりします。

もしよければ、僕のユーザコード「SW4188」に、フレンド申請をお願いします。

フレンドになれば、登録したフレンドといつでも対戦することが出来るようになります。
対戦には相手がアプリを開く必要がありますが、フレンド対戦だと相手のゴースト（相手の記録に沿ったコンピュータ）と対戦することも出来ます。