(ΦωΦ)＜yukicoder No.774 tatyamと素数大富豪

$1$ から $13$ までのいずれかの数が書かれているカードが $n$ 枚あり、$i$ 番目のカードの数は $a_{i}$ です。
これらを一列に並べてなるべく大きな素数を作りたいとき、その素数を求めてください。
どう並べても素数にならないときは、それを指摘してください。
・$1 \le n \le 9$
・数列 $a$ はソートされている。

ミラー・ラビンが競プロに出にくいことの一因となっていそうな題材で、
ミラー・ラビンが何故競プロに出題されにくいかというと、ひとえに乱択だからだと思う。

普通競プロで考える範囲は long long までで、それだと決定的に判定できるけれども、
一般にはミラー・ラビンといえば乱択だし、ミラー・ラビンが速いとはいえ今回のようなケースだとうまくやらないと TLE する可能性もある。
ミラー・ラビンを乱択で実装していたとして、もし TLE したらだいたいの人間は乱択の試行回数を減らすわけで、
「大丈夫なんかこれ」というような試行回数でもこの問題だと通ってしまう。落とせそうなケースも見つけづらい。
正解不正解の線引きが難しいアルゴリズムなんだと思う。

この問題でうまくやるには、まず大小関係を確認してミラー・ラビンをなるべくしないのが良い。
ミラー・ラビンって結構時間かかるよというのは覚えておきたい。

ちなみに、入力の最大値は int('13' * 9) の $57$ ビットで、この範囲で正常に動く実装であれば問題ない。

(ΦωΦ)＜おしまい