atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ 整数論 素数 素数定理 Euler の totient 関数 解説動画はこちらです． 1. 概要 競技プログラミングの学習をしていると，次のような結果を目にすることがあると思います． $N$ 以下の素数の個数は $\displaystyle \frac{N}{\log N}$ 程度である（素数定理）． $N$ 以下の素数の逆数の総和 $\displaystyle \sum_{p\leq N}\frac{1}{p}$ は $\log\log N$ 程度である（Mertens の定理）． なお，本記事では $p$ と書けば素数を表すものとし，$N$ 以下の素数に対する和を $\displaystyle \sum _ {p\leq N} \frac{1}{p}… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fprime_related_complexity" title="素数に関する評価 - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:10:58 rich https://info.atcoder.jp/entry/algorithm_lectures/prime_related_complexity 1.0 100%