はじめに

https://atcoder.jp/contests/abc339/tasks/abc339_f
この問題を解いていて、解説放送のコードで「10^9以下の数字をランダムに求めて、その値が素数となるまで繰り返す」という操作を10回行っていてなぜTLEしないのか疑問に思い、質問して解決したので記事にしたいと思います。

内容

まず、10^9以下の素数の個数を求めます。これは「50847534」で、だいたい「5×10^7」なので、5×10^7個とします。
https://2357.aimary.com/total_prime.html

次に、一回の操作で素数が現れる確率を求めます。これは「素数の個数/全体の個数」なので、「(5×10^7)/(10^9)」となります。これを通分すると、「1/20」となります。

「一回の操作で素数が現れる確率」を元に、「一回の操作で素数が現れない確率」を求めます。これは「1-(一回の操作で素数が現れる確率)」なので、1-(1/20)となり=(19/20)です。

ここから100回ランダムに出力する操作を行うとします。そうすると「100回の操作で一度も素数が現れない確率」は
「(19/20)^100」となります。これを計算してみます(wolfram alphaくんにお願いしました)

結果はだいたい「0.005」という値になりました。つまり
「100回の操作で一度も素数が現れない確率」は「0.5%」です。

ここで元々何を求めたかったかというと、「TLEしない理由」だったので、TLEする回数について考えます。TLEするこの操作回数をだいたい10^9回とします(素数判定を毎回するのでもう少し小さくなるはずです)。
となると、「10^9回の操作で一度も素数が現れない確率」となり、上で求めた話を持ってくると、100回の時点で、0.005だったので、10^9回になったらとんでもなく確率が小さくなりそうなのがなんとなくわかると思います。
以上です。

まとめ

というわけで「10^9以下の値をランダムに生成して、値が素数になるまで操作を繰り返すときTLEしない理由」がわかりました。
ちなみに(0.005)^(10^9)をwolfram alphaくんにお願いするとよくわからない答えになるので(0.005)^(10^5)でお願いすると
1.0009989037986941668162647131933062484993475083057800492... × 10^-230103
という答えが返ってきます。ものすごく小さい確率なのはわかるけどそれ以外のことはよくわからないですね！()

質問に答えていただいたsnukeさんに感謝です。土下座しますorz
https://www.youtube.com/live/Cw29uys1JV0?si=0KDavcDEjGA0TvpV&t=11242