Skip to content

Zhou's Sieve

Prerequisites

Definition

The Zhouge Sieve is a sieve method that can compute the prefix sum of most multiplicative functions in sublinear time complexity.

The following will take solving \(\displaystyle\sum_{i=1}^nf(i)\) as an example to elaborate on the principle of the Zhouge Sieve.

Conventions

  • \(\mathbb P\) denotes the set of prime numbers, and \(p_i\) denotes the \(i\)-th prime.
  • \(m\) denotes the number of primes within \(\sqrt n\).

Requirements

When \(p\in\mathbb P,c\in\mathbb N\), \(f(p^c)\) is a low-degree polynomial in \(p\).

Idea

  • For any integer in \([1,n]\), it has at most one prime factor \(>\sqrt n\).
  • Utilize the property that \(\left\lfloor\dfrac ni\right\rfloor(i\in[1,n]\cap\mathbb N)\) has only \(O(\sqrt n)\) distinct values to reduce time complexity.

Process

Divide all integers in \([1,n]\) into two categories based on whether they have a prime factor \(>\sqrt n\):

\[ \sum_{i=1}^nf(i)=\sum_{i=1}^n\left[\exists d\in(\sqrt n,n]\cap\mathbb P,d\mid i\right]f(i)+\sum_{i=1}^n\left[\forall d\in(\sqrt n,n]\cap\mathbb P,d\nmid i\right]f(i) \]

For the first part, enumerate the largest factor. According to the properties of multiplicative functions, it can be transformed:

\[ \sum_{i=1}^nf(i)=\sum_{i=1}^{\sqrt n}f(i)\cdot\left(\sum_{d=\lfloor\sqrt n\rfloor+1}^{\lfloor\frac ni\rfloor}[d\in\mathbb P]f(d)\right)+\sum_{i=1}^n\left[\forall d\in(\sqrt n,n]\cap\mathbb P,d\nmid i\right]f(i) \]

The two parts can be computed separately.

Part 1

Compute \(\displaystyle\sum_{i=1}^{\sqrt n}f(i)\cdot\left(\sum_{d=\lfloor\sqrt n\rfloor+1}^{\lfloor\frac ni\rfloor}[d\in\mathbb P]f(d)\right)\).

Consider enumerating \(i\), then compute the part inside the parentheses in \(O(1)\).

Let \(\displaystyle g(t,l)=\sum_{i=1}^l[\forall j\in[1,t],\gcd(i,p_j)=1]f(i)\), i.e., the sum of \(f\) values of numbers in \([1,l]\) that are coprime to \(p_1,p_2,\dots,p_t\).

Thus, the computation of Part 1 becomes \(\displaystyle\sum_{i=1}^{\sqrt n}f(i)\cdot g\left(m,\left\lfloor\frac ni\right\rfloor\right)\).

Boundary: \(g(0,l)=\sum_{i=1}^lf(i)\). Transition: \(g(t,l)=g(t-1,l)-f(p_t)\cdot g\left(t-1,\left\lfloor\frac l{p_t}\right\rfloor\right)\).

There are \(O(\sqrt n)\) distinct values for \(l\). For each value, its prime factors need to be enumerated, so the complexity is \(\displaystyle O\left(\frac{\sqrt n}{\ln\sqrt n}\cdot\sqrt n\right)= O\left(\frac n{\log n}\right)\), which requires optimization.

Note that when \(p_{t+1}^2>l\), the only number satisfying the condition is \(1\), so \(g(t,l)=f(1)=1\).

Substituting into the recurrence gives: when \(p_t^2>l\), \(g(t,l)=g(t-1,l)-f(p_t)\).

Therefore, stop the transition once \(p_t^2>l\) is detected. Denote this \(t\) as \(t_l\). Then \(\forall t>t_l,g(t,l)=g(t_l,l)-\sum_{i=t_l}^{t-1}f(p_i)\).

Precomputing the prefix sum of \(f\) values for primes allows quick computation of \(g\). The time complexity is optimized to \(O\left(\dfrac{n^{\frac34}}{\log n}\right)\).

Part 2

Compute \(\displaystyle\sum_{i=1}^n\left[\forall d\in(\sqrt n,n]\cap\mathbb P,d\nmid i\right]f(i)\).

Let \(\displaystyle h(t,l)=\sum_{i=1}^l\left[i=\prod_{j=t}^mp_j^{c_j},c_j\in\mathbb N\right]f(i)\), i.e., the sum of \(f\) values of numbers in \([1,l]\) whose prime factors are only among \(p_t,p_{t+1},\dots,p_m\).

Part 2 is exactly \(h(0,n)\).

Boundary: \(h(m+1,l)=1\). Transition: \(\displaystyle h(t,l)=h(t+1,l)+\sum_{c\in\mathbb N^*}f(p_t^c)\cdot h\left(t+1,\left\lfloor\frac l{p_t^c}\right\rfloor\right)\).

There are \(O(\sqrt n)\) distinct values for \(l\), so direct transition has complexity \(\displaystyle O\left(\sqrt n\cdot\frac{\sqrt n}{\ln\sqrt n}\right)= O\left(\frac n{\log n}\right)\), which requires optimization.

Similar to the optimization for \(g\), note that when \(p_t>l\), the only number that can be formed using \(p_t,p_{t+1},\dots,p_m\) is \(1\), so \(h(t,l)=f(1)=1\).

Similarly, it can be derived that \(\forall p_t^2>l,h(t,l)=h(t+1,l)+f(p_t)\).

Therefore, stop the transition once \(p_t^2>l\) is detected. Denote this \(t\) as \(t_l\). When \(h\) is needed later, add \(\displaystyle\sum_{i=p_{t_l}}^{\min(l,\sqrt n)}[i\in\mathbb P]f(i)\) to the current \(h\) value.

The time complexity is optimized to \(O\left(\dfrac{n^{\frac34}}{\log n}\right)\).

Summation

After computing the answers for Part 1 and Part 2, their sum is \(\displaystyle\sum_{i=1}^nf(i)\).

References

Notes on Linear Sieve / Du Sieve / Zhouge Sieve for Multiplicative Functions | Bill Yang's Blog

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用