Document

CodeIQ 「コード・トライアスロン」解法
Kawazoe (@riverplus)
■ 第１問
本問は、解くだけなら何ら造作ない問題だと思います。
変数の桁あふれに注意してコードを組んでください。
以下では、問題の背景について紹介します。
本問は、ペラン数列という数列を題材にしました。
この数列は、なかなか興味深い性質を持つ数列です。
題意のような、F(n) が n で割り切れるときの n の値をいくつか並べてみましょう。
なんと、素数の数列になっているのです。
実際にはそのような n がすべて素数になるわけではないですが、n = 271441 まではすべてが素数です。
具体的な計算については下記のページなどをご覧下さい。
http://www.suguru.jp/Fibonacci/MonsterPerin.html
(3/31 修正) 上のページには若⼲誤りが含まれているようです。
こちらのページも合わせてご覧下さい。（yuppe19 さん情報 Thanks！）
http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun321.htm
■ 第２問
素因数分解を試し割りのアルゴリズムで⾏うときと同じ要領で解ける問題です。
対象の数を、まずは 2 でこれ以上割り切れなくなるまで割り尽くします。
次にその商を 3 で割り尽くします。
さらにその商を 4,5,6,・・・の順で割りつくしていけば、最後に割り切れたときの割る数が、答えとなります。
■ 第３問
素数かどうかの判定を何回も⾏う必要がある問題です。
もっとも簡単な素数判定のやり⽅は、2 以上の数で⼀つずつ割ってみる試し割りです。
ですがこれだと、何回も素数判定を⾏う場合は⾮効率になってしまいます。
そこで、エラトステネスのふるいなどを⽤いて、素数判定を⼀瞬で⾏える準備をしてから、
素数番⽬の素数を探すアプローチをとりましょう。
（なお、すみませんが、本問の公開終了⽇までは、この URL を周りに教えないよう、ご協⼒お願いします。）

Download Report