素数大富豪をプログラミング的に考えてみる


先日素数大富豪のアプリをリリースしました。

残念ながら1人では遊べないのでCPU対戦とか、デバッグで使用してた練習用機能のアプリ化とかを考え中。

今回は素数大富豪をプログラムとしてどう扱うかの雑感です。

組み合わせ

素数大富豪は基本的に最初11枚配られる。

最初に選べる数字は 11P1+…+11P11=108505111 通り。

11枚から5枚出しまで考慮するなら11P1+…+11P5 = 64471通り。

ランダムなら問題ないけどほとんどの組み合わせは素数ではないのでCPU的には成功か失敗を最初に決めてから出す数を決める必要がありそう。

素数判定

素数かどうかの計算はPCならともかくスマホだと重い。

素数かどうかを判定するにはアルゴリズムで計算する他にないのか。

例えば素数リストを作ってみるとか。

  • 巨大な bool 配列を作ってインデックスに合わせ true/false を入れて判定に使う
    • 巨大で素な行列になる (11枚時の最大値は1313131312121212111111)
    • bool は1バイトだから1ゼタバイト?
  • Listに素数を詰め込んで Contains() で判定する
    • 8桁未満の素数の数は664579個あった
    • 8桁の素数の探索が全然進まないので22桁の素数なんてできる気がしない

まあ無理そう。

所感

サーバを用意してそこでマッチングさせればCPUは必要ないし、重い処理もサーバにやらせればいいしで全部解決する。

次の問題はそれをするにはお金も技術力が足りない。

ちなみに11枚の最大値でとんでもない数が出てきたけど、ulongの最大値(18446744073709551615)を超えてるので分割して計算するアルゴリズムにしないと対応できない。

まあそもそも処理できるような大きさではないので無問題。

しかし素数出しだけでこんな感じなら合成数出しとか指数出しとか考えたらきりがなさそうに思える。

 


コメントを残す

メールアドレスが公開されることはありません。