⚠️ 発展的な内容を含みます。

\(\gdef\floor#1{\lfloor#1\rfloor}\)

\(n\) 以下の素数の個数を \(\pi(n)\) と書きます。また、\(S(n)\) を下記で定義します。

\[S(n) = \{1, 2, \dots, \floor{\sqrt{n}}\} \cup \{\floor{n/1}, \floor{n/2}, \dots, \floor{n/\floor{\sqrt{n}}}\}.\]

前提として、与えられた \(n\) に対して、各 \(i \in S(n)\) における \(\pi(i)\) を求めるのは（全体で）\(O(n^{2/3})\) 時間や \(O(n^{2/3}/\log(n)^{1/3})\) 時間で可能です。

see also: 関連スライド

\(p^8\le N\) なる素数の個数は愚直に求めても \(O(N^{1/8})\) 時間なので、無視できます。

\(p^2 q^2 \le N\) (\(p\lt q\)) なる素数のペアに関して考えます。\(p\) を固定したとき、\(p\lt q\le \sqrt{N}/p\) であるので、\(p\) 以下の素数と \(\sqrt{N}/p\) 以下の素数を数えられればよいです。\(q\) の整数性などから、\(\pi(\floor{\floor{\sqrt{N}}/p}) - \pi(p)\) に等しいです。

note: \(i\) 番目の素数 \(p_i\) に対して \(\pi(p_i) = i\) なので、\(\pi(p)\) の項は簡単に求められます。

よって、各 \(i\in S(\floor{\sqrt{N}})\) における \(\pi(i)\) を求めておけばよく、これは \(O(\floor{\sqrt{N}}^{2/3}) = O(N^{1/3})\) 時間で可能です。

\(p\lt q\) なので \(p\lt N^{1/4}\) の範囲で和を取ればよく、（上記の前処理により各項は \(O(1)\) 時間で求められるので、前処理の計算量に応じて）全体で \(O(N^{1/3})\) 時間や \(O(N^{1/3}/\log(N)^{1/3})\) 時間などになります。

提出 #60552451, 1 ms