Skip to content →

素数の個数

Lucy’s DP

包除原理より \(n\) 以下の素数の個数 \(\pi(n)\) は
\begin{align}
\pi(n)=\sum \mu(d) \lfloor n/d \rfloor \\
\end{align}と書ける。

\(n\) を固定する。\(\lfloor n / i\rfloor\) を基底とする整数係数の加群 \(V\) を考えて \(\boldsymbol{v} = \sum a_i \lfloor n / i\rfloor\) に対する作用素 \(D_m\) を \(D_m \boldsymbol{v} = \sum a_i \lfloor n / (im)\rfloor\) と定義する。\(\mathbb{N}\) と \(V\) の元を区別して、\(\sum a_i \lfloor n / i\rfloor\) は \(\sum a_i\boldsymbol{e}_{i}\) のように書くべきかもしれないが、分かりやすいので混同する。
\(i\) 番目の素数 \(p_i\) を用いて \(f_i = 1 – D_{p_i}\) とすると $$\pi(n) = \left(\prod_{i=1}^\infty f_i \right) \left\lfloor \frac{n}{1} \right\rfloor $$ になる(左辺と右辺で型が違いますが、自然に解釈してください)。合成数 \(m\) の素因数には \(\sqrt{m}\) 以下のものが必ず存在するから、\(p_i^2 \leq n\) となる最大の \(i\) を \(k\) と置くと$$\pi(n) = \left(\prod_{i=1}^k f_i \right) \left\lfloor \frac{n}{1} \right\rfloor $$である。

結合法則が成り立つので \(f_i\) を順に作用させて
$$\pi(n) = f_1\left(f_2\left(\cdots \left(f_{k-1}\left(f_k\left\lfloor \frac{n}{1} \right\rfloor\right)\right)\right)\right) $$
の順に計算する。\(\left\lfloor \frac{n}{d} \right\rfloor\) の形の基底は \(O(\sqrt n)\) 個しか存在しない。また、\(d < p_m^2\) ならば \(\left(\prod_{i = 1}^m f_i \right) \left\lfloor \frac{n}{d}\right\rfloor = \left(\prod_{i = 1}^{m-1} f_i \right) \left\lfloor \frac{n}{d}\right\rfloor\) なのでそのような基底に対しては \(f_m\) は恒等作用素として扱ってよい。つまり、dp の更新は in-place に行い \(d < p_m^2\) となる基底には何もしない。

  • \(d \leq \sqrt{n}\) となる基底 \(\left\lfloor \frac{n}{d}\right\rfloor\) に対して、恒等でない作用が \(O(\sqrt{n/d})\) 回起きる。作用の回数の和は \(O\left(\int_{x=1}^{\sqrt{n}} \sqrt{n/x}dx \right) = O(n^{3/4})\)。
  • \(d \geq \sqrt{n}\) となる基底 \(\left\lfloor \frac{n}{d}\right\rfloor\) に対して、恒等でない作用が \(O(\sqrt{n/d}) = O(n^{1/4})\) 回起きる。このような基底は \(O(\sqrt{n})\) 個しかないので、作用の回数の和は \(O(n^{3/4})\)。

Meissel-Lehmer algorithm

結合法則が成り立つので \(f_i\) を順に作用させて
\begin{align}
\pi(n) &= f_1f_2\cdots f_{k-1}\left(f_k\left\lfloor \frac{n}{1} \right\rfloor\right) \\
&= f_1f_2\cdots f_{k-1}\left(\left\lfloor \frac{n}{1} \right\rfloor – \left\lfloor \frac{n}{p_k} \right\rfloor\right) \\
&= f_1f_2\cdots f_{k-1}\left\lfloor \frac{n}{1} \right\rfloor – \pi\left(\left\lfloor \frac{n}{p_k} \right\rfloor\right)\\
&\vdots\\
&= f_1f_2\cdots f_{l}\left\lfloor \frac{n}{1} \right\rfloor – \sum_{i=l+1}^k \pi\left(\left\lfloor \frac{n}{p_i} \right\rfloor\right)\\
\end{align}を得る。ただし、\(p_i^2 \leq n\) となる最大の \(i\) を \(k\)、\(p_i^3 \leq n\) となる最大の \(i\) を \(l\) と置く。
上の式変形で \(f_1 f_2 \cdots f_{k-1}\left\lfloor \frac{n}{p_k} \right\rfloor\ = \pi\left(\left\lfloor \frac{n}{p_k} \right\rfloor\right)\) となるには \(p_{k}^2 > \left\lfloor \frac{n}{p_k} \right\rfloor\) でなければならないが、これはベルトラン=チェビシェフの定理から従う。あるいは、包除原理から解釈してもよい。\(\sum_{i=l+1}^k \pi\left(\left\lfloor \frac{n}{p_i} \right\rfloor\right)\) は \(n^{2/3}\) 以下の数に対してエラトステネスの篩を適用すれば計算できる。\(\left\lfloor \frac{n}{d} \right\rfloor \leq n^{2/3}\) となる基底に対しては、それ以上作用素を掛けずそのままにして、計算を進めると、$$f_1f_2\cdots f_{l}\left\lfloor \frac{n}{1} \right\rfloor = \sum_i \sum_{\left\lfloor \frac{n}{d} \right\rfloor \leq n^{2/3}} a_{i, d} f_1f_2 \cdots f_i \left\lfloor \frac{n}{d}\right\rfloor + \sum_{d < n^{1/3}} b_d \left\lfloor \frac{n}{d}\right\rfloor $$と展開できる。\(\left\lfloor \frac{n}{d} \right\rfloor > n^{2/3}\) となる基底は \(O(n^{1/3})\) 個しかないので、\(O(n^{2/3})\)で展開できる。\(f_1f_2 \cdots f_i \left\lfloor \frac{n}{d}\right\rfloor\)は\(\left\lfloor \frac{n}{d}\right\rfloor\)以下の数のうち、\(p_1, p_2, \ldots, p_i\) で割り切れないものの個数だから、累積和を高速に得られるデータ構造(BITなど)でエラトステネスの篩を管理すれば、\(O(n^{2/3}\log(n))\) で列挙できる。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA