軽めの記事です。 \(n\) 番目の素数を \(p_n\)、\(n\) 以下の素数を \(\pi(n)\) と書くとします。 このとき、\(p_n\) は \(\pi(p_n) \ge n\) かつ \(\pi(p_n-1) \lt n\) を満たします。 よって、これは二分探索で求められます。 上限を決めるのが大変そうで…

別に、おふとんから出たくない朝とかに数えてもいいと思います。 \(n\) 以下の素数の個数を数えたいときどうしますか？ 各整数 \(2\le i\le n\) に対して素数判定して数えます？ 素数判定を試し割り法でやると \(\Theta(n\sqrt{n})\)、線形篩*1を使えば \(\T…

どうしてこんなことに... まえおき 本題 リテラルのつくりかた std::max scanf / printf int8_t ACL の話 そもそも定義されない処理系もある そのほか むかしの まえおき C++ には次の型があります： signed char unsigned char char short signed int (= sh…