チームラボ天下一武道会（アルゴリズムコンテスト）
1月23日にチームラボでアルゴリズムコンテストがあったそうです
http://twitter.com/teamlab_tech/status/8104556580
課題は 1000万個目の素数の値を出すまでの処理時間 で、良くある問題なのですが
なんと優勝したのがうちの研究室にいる@chkfj君の１秒だったそうで。。おめでとう！
制限時間3時間を利用してどの言語でも良いのでできるだけ早く求めた人が優勝
もちろん素数データの利用やwebAPIの利用も禁止ということでガチで計算して1秒とかどうやるんだよ…
と思い自分も挑戦してみました。
ちなみに結果の詳細は
http://twitter.com/teamlab_tech/status/8137826526
だったそうです。上位陣はみんな エラトステネスの篩（ふるい） を利用していたそうです、早いんですね。
自分は最初JAVAで書いてみたのですが計算速度があまりにも遅いので（原因はアルゴリズムがダメだった意外に他ならないんですが）、やはりCが早いと言うことで途中からCに変えました。
エラトステネスの篩で実装したのですが何故かかなり計算が遅く話になりませんでした…たしか20分くらいかかってた気がする。
どう見てもアルゴリズムがエラトステネスの篩じゃなかったんですけどね！！
ということで早いと噂のMiller-Rabinテストを利用してみたのですがこれでも3分ちょっとかかってしまいました。
ということでCの1秒どころかJAVAの7秒すら足元にも及ばない結果になってしまいました。。。
@chkfj君に聞いたところMiller-Rabinテストは単体の素数に対しての計算はエラトステネスの篩より早いけど1から数え上げるのはエラト（ｒｙの方が断然早いらしいです。
というわけでみなさまお疲れ様でした、機会があればいつか参加したいですね！
