素数大富豪判定アプリを作ってみたお話
この記事は 素数大富豪 Advent Calendar 2018 6日目の記事です。
昨日はbutchi_yさんの「素数大富豪研究のためのMathematicaユーティリティー関数」でした。
素数大富豪研究のためのMathematicaユーティリティー関数 - Qiita
初めまして！
twitterと素数大富豪と競技プログラミングをしている高校生のtatyamと申します。
私からは自作素数判定アプリの紹介をしてみようと思います。
作った経緯
プログラミングしたい！！
↓
Mac買ってもらった！！
↓
アプリ作ろう！！
↓
素数大富豪ディーラー作ろう！！
再現できました
デザインが全部デフォルトで、コードも難しくはないのでできてしまいました。*1
デザインが良くない？
アプリの作り方は分かってきたので作り直し。
電卓を参考にして良い感じにできました。*2
機能
素数判定・素因数分解
入力された数字について素数判定を行います。入力の限界は約20億桁ですが、その前に性能の限界になるでしょう。
素数判定はBigIntegerのisProbablyPrime(Miller-Rabin素数判定法)を利用しています。
これは確率的素数判定法ですが、合成数を素数と判定する確率は よりずっと小さいので問題ないでしょう。計算量は
です。
詳細はWikipediaがわかりやすいかと思います。
また、素因数分解にはPollard-Rho法を利用しています。
これすごくないですか？？とっても速いです。計算量はです。
Xを入れてまとめて探索
Xを入れて素数判定をすると、Xに0~Kを入れてまとめて判定できます。*3
3つまでXを入れられます。
4つ子も九方美人も1画面に出すことができます。
コックさん素数もまとめて探索できます。
並べ替え最大素数の探索
判定ボタンを長押しすると、並べ替え最大素数を表示してくれます。Xを1つだけ入れることができます。
54枚入れても、1秒はかからない自信があります。(※最新の機種の場合)
計算量はです。*4
タイマー
1手ごとの時間のほか、1人ごとの持ち時間を設定することができます。
今後の予定
- 採譜モードをつくる
素数判定しながら採譜ができるというのを目指しています。
これができたら公開しようかな…？
- iOS版について
実は最低限の部分だけはできています。公開にはApple Developer Program ($99/年) が必要なので支援をいただこうかな？と思っています。*5
フォントが素晴らしい…
さいごに
欲しい！と思っていただけた方、DMお待ちしております。
tatyam@JOIに向けて精進 (@tatyam_prime) | Twitter
すでに持っている方も、もう一度ダウンロードしてアップデートをお願いします。
とあるコンテストに素数大富豪の問題を出すことにしたので解いてほしいなー((o(ΦωΦ+)o))
Advent Calendar Contest 2018 - yukicoder
明日はでこぽんさんの「MathPowerで語呂素数ガチャつくった話」です！.+ﾟ(o(｡・д・｡)o).+ﾟﾜｸﾜｸ
