約数の個数のオーダー
約数を全列挙するには$ O(\sqrt N)かかるが、約数の個数自体はそれよりずっと少ないはず。
ググってみるとこういう記事があった。
これによると、$ O(N^{\frac{1}{\log \log N}})個らしい。
これは$ O(\sqrt N)より小さく、$ O(\log N)よりは大きい。
一体どれくらいかわからないので、実際に約数の個数を調べてみる。
……調べてみようと思ったが、これは高度合成数の話になる。
そういうわけで高度合成数をいくつか挙げて、それ以下の整数における約数の個数の最大値の表を作ってみた。
table:高度合成数
上限 約数の個数の最大値 高度合成数 高度合成数の個数
100 12 60 9
10³ 32 840 15
10⁴ 64 7560 20
10⁵ 128 83160 29
10⁶ 240 720720 38
10⁷ 448 8648640 47
10⁸ 768 73513440 56
10⁹ 1344 735134400 66
10¹⁰ 2304 6983776800 76
10¹¹ 4032 97772875200 86
10¹² 6720 963761198400 95
10¹³ 10752 9316358251200 106
10¹⁴ 17280 97821761637600 117
10¹⁵ 26880 866421317361600 125
10¹⁶ 41472 8086598962041600 135
10¹⁷ 64512 74801040398884800 146
10¹⁸ 103680 897612484786617600 156
素因数の種類数
ついでに素因数の種類数も調べてみた。
table:上限以下の自然数で、素因数の種類数が最大になる最小の自然数
上限 自然数 素因数の種類数
100 30 3
10³ 210 4
10⁴ 2310 5
10⁵ 30030 6
10⁶ 510510 7
10⁹ 9699690 8
10¹⁰ 6469693230 10
10¹² 200560490130 11
10¹⁸ 614889782588491410 15
素数を小さい順にかけるとできる。
$ \log(N)っぽい。