素数に関する評価
#競技プログラミング
https://info.atcoder.jp/entry/algorithm_lectures/prime_related_complexity
$ N
以下の素数の個数は、
$ \frac{N}{\log N}
個程度
$ N
以下の素数の逆数の総和
$ \sum_{p \le N}{\frac{1}{p}}
は、
$ \log\log N
程度
小さい方から
$ N
番目の素数は、
$ \Theta(N \log N)
正の整数
$ n
の相異なる素因数の個数を
$ \omega(n)
とするとき、
$ \omega(n) \in O(\frac{\log N}{\log\log N})