寄り道中 [TopCoder] Marathon Match 58

TopCoderと呼ばれる、定期的にプログラミングコンテストを開催しているサイトを知りました。

英語オンリーなので私も全然訳が分かってないのでTopCoderの詳しい説明はGoogleに任すとして
プログラムに点数が付いて競い合う事ができるというのは、
プログラミング好きにとってこれほど楽しい遊びはないって感じですね！
これを10年前に知っていたらさぞかし熱中しただろうと思います。
世の中には面白い物が色々あるもんですね。


それで、楽しそうなので私もちょっとだけ参加してみました。
いくつかあるコンテストのうち、
2週間くらいの間に一つの問題を解決するプログラムを作る
Marathon Matchと言うコンテストです。


問題
与えられた a, b, x で、 素数p に対して、(p - a) から (p + b) の範囲で x 個の素数がある(x個にpを含む)、 という最小の p を求めよ。（このサイトの引用です）

（勢いで参加してみたものの、英文の問題が理解しきれずギブアップする所でしたｗちなみに、自分で英語を読んだ時は、x-isolatedが理解できず詰まってました…）



素数？

ソスウ

そすう…

primeと言えば、ドコモの携帯しか連想しませんよ？
私の普段生活には素数とか出てきませんからｗ
あまりにも素数の事を知らなかったので、まず検索して勉強です。

エラトステネスの篩
フェルマーテスト
ミラーテスト
素数定理


ふむふむ、なるほどなるほど、
問題では2〜2^63-1もの広大な範囲の中から素数を探すので
きっともっと数学的な何かや、プログラミング的（アルゴリズム的）何か
を知っていないと勝負にならないとは思いますが
これだけ分かればとりあえず何か作れそうです。


で、作ってみたプログラムを提出してみたところ
100点中9点（ﾌﾟｯ

http://www.topcoder.com/longcontest/?sc=&sd=&nr=100&sr=101&rd=14226&module=ViewStandings


結果はともあれ、これは楽しいですね。
モチベーションをどう保つのか？と言う問題もありますが
たまには、こういう脳の体操的な事はやった方がいいなぁ
って思いました。