既存の素数大富豪のアプリをみてみると2人対戦(人間VSコンピュータ)の場合、カードを全部配るのではなく、7~13枚になっています。ルールでは最初のカードの枚数は素数であることが望ましいとしています。

では仮に13枚のカードが配られた場合、それをうまく組み合わせれば素数になるかもしれない場合があるのですが、それはどのような場合なのでしょうか?

枚数毎の最大素数大富豪素数を求める – Qiitaをみてみると13枚のカードで作ることができる最大の素数は13131313131312121110111211です。この数は前回の素数判定法では調べることはできません。引数がlong型で表せる数を超えているからです。ではどうするか? 素数でして出せるカードの枚数を制限するしかなさそうです。だいたいこういう領域でコンピュータに本気を出されたら人間には勝ち目はありません。

比較的小さな数で割りきれることがわかった場合、すぐに素数でないという結果が返ってきますが、素数であるという結果は3以上の奇数でこれ以上やっても意味が無いと見なされる数まで繰り返されるので時間がかかります。実際に素数を渡してみて素数であるという結果が返されるのは13桁くらいまでです(13131313131113が素数であるという結果はすぐに返される)。それ以上だとちょっと厳しいです。

そこで勝手ながら当サイトで作成する素数大富豪では素数として出すことができるカードの枚数は7枚までに限定することにします。

次にコンピュータが次に出すカードを選ぶアルゴリズムですが、手持ちのカードの組み合わせで最小のものを選ぶことにします。また合成数だしもできるようにするには素因数分解も必要です。そこで素因数分解のアルゴリズムを考えます。

N枚出しをする状況で手持ちのカードの組み合わせは何があるか?
その中で素数になるものはあるか?
素数が見つからない場合は合成数出しをできないか考えてみる

このように考えます。実際にゲームに勝つという観点ではダメダメなアルゴリズムですがご容赦ください。

N枚出しをする状況で手持ちのカードの組み合わせは何があるか?

初期のカードの枚数は13枚でコンピュータはミスをしないものとします。実際の素数大富豪ではあえて素数ではないものを出してカードを獲得するという駆け引きもあるそうなのですが、いまは考えないことにします。

出せるカードの組み合わせがどれだけ存在するかは順列を考えればよいことになります。最初のカードは13枚なので最大7枚出せると仮定すると全部で、13×12×11×10×9×8×7 = 8,648,640とおりになります。

ではそのような順列を生成するクラスを作成してみましょう。

これで以下のようなコードを書いて実行してみると確かに動作していることがわかります。

問題はカードの数を増やしたときです。これだと結構な時間がかかります。ゲームにはなりません。

そこでコンピュータが出せるカードは4枚までに制限します。

コンピュータが持っているカードで出せるカードを調べるために必要な時間は?

そして試しにカードを適当に配って(この方法では同じ数字のカードが5枚以上配られる可能性があるが・・・)1~4枚の組み合わせで素数がどれくらい存在するか、合成数の場合、素因数分解可能かどうかを調べるためにどれくらい時間がかかるか調べてみましたが、ほぼ一瞬で処理は終わりました。

実行するたびに結果は変わりますが、素数は1500~2000,素因数分解可能な合成数は500~1500くらい存在することがわかります。ただし素因数がカードのなかに含まれるかどうかのチェックはいい加減な方法でやっているのでもう少し時間がかかるかもしれません。