素数判定の上辺

ニコニコ動画のごちうさ１羽　200万再生を気にごちうさを見直しました。

そこで、ごちうさ第１０羽『対お姉ちゃん用決戦部隊、通称チマメ隊』で、ココアがシャロと素数を言い合うシーンが印象に残った（おかしい）。
ココアが「じゃあどっちがたくさん素数言えるか勝負だよ！」と言い素数を「2,3,5….9697,9719」まで言いました。9719は1198番目の素数である。
つまり作中ではカットされているが、ココアは1198番目までの素数を言い続けたことになる。

まぁそんなことをきっかけに素数判定について少し調べた。

そもそも

素数 　#とは
1と自分自身以外に正の約数を持たない自然数で、１でない数のことを指す。

素数判定　#とは
ある自然数 n が素数であるか合成数であるかを判定する問題である。
素数判定を行うアルゴリズムのことを素数判定法という。

ココアは素数を暗記しているのか。それとも数字を全て脳内で判定してるのか。
なーんて、くだらないことを考えながら調べてた。

どうやら素数判定法には大まかに『決定的（確定的）素数判定法』と『確率的素数判定法』の二通りあるらしい。

決定的（確定的）素数判定法(deterministic primality test)　#とは
与えられた自然数nが「素数」か「否」を判定する判別法.
多項式時間アルゴリズムは存在しないとされてきたがAKSが発見された.

確率的素数判定法(probabilistic primality test)　＃とは
与えられた自然数nを「合成数である」または「判定不能」か判別する判別法
いろいろな条件のもとで「判定不能」と判定されればその数を素数として扱うことができる。
多項式時間アルゴリズムであることが知られている。

□決定的素数判定法

・試し割り
与えられた自然数nを「素数」と仮定し、2から1ずつ数字を増やし、その数を自然数nで剰余し0になった時点で「素数でない」と判明した時点で終了する。

・エラトステネスの篩
指定された整数以下のすべての素数を発見するための単純アルゴリズムである。
判定する数より小さな値全てを使って除算を行い、その剰余を調べることで判定する。
(1)「素数の倍数は素数ではない」
(2)「素数でない数つまり合成数は必ずその数の平方根以下に分解できる。」
数字のリストを作成し、(1)(2)の性質を利用し、数字のリストから合成数を篩い落とし残った数字のリストが素数リストである。
(具体的な流れはwikipediaのGIFアニメーション見た方がいい。)
・関連としてサンダラムの篩やアトキンの篩がある。

・AKS素数判定法
与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる世界初のアルゴリズム

この辺まで調べて力尽きました

□確率的素数判定法

・Fermat
・Solovay-Strassen
・Miller-Rabin

決定的素数判定法と確率的素数判定法

少し調べてたつもりが頭抱えてた
　　　Λ_Λ　:::::::
　　/彡ミﾍ )ー､ ::::
　 /:ﾉ: ヽ ＼::|　:::
　/:｜:: ＼ ヽ|　:::
￣L_ﾉ￣￣￣＼ノ￣￣

( ˘•ω•˘ ).｡oஇ

また、素数の個数については「素数定理」を用いることによって大体がわかる。

素数定理　#とは
自然数の中に素数がどのくらいの「割合」で含まれているかを述べる定理である。

エラトステネスの篩あたりは初学者向け参考書の問題とかによく書かれているイメージがあったりするぞい
※各判別法の詳しい考え方やアルゴリズム・歴史については本・論文を参考に。
（間違っていたら指摘して下さると幸い。）

つまり

何が言いたいかというとココアはすごいな　ってことです

私も『どっちが多く素数を言えるか』ココアと勝負したい❤️