Min_25 Sieve
Definition
Because of the idea behind it, this sieve is also known as the Extended Eratosthenes Sieve.
It is called the Min_25 sieve because Min_25 invented it and was the first to use it.
Properties
It computes prefix sums of a class of multiplicative functions in \(O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right)\) or \(\Theta\left(n^{1 - \epsilon}\right)\) time.
Requirements: \(f(p)\) is a sum of completely multiplicative functions of \(p\) that can be evaluated quickly (a polynomial, for example), and \(f(p^{c})\) can be evaluated quickly.
Notation
- Unless stated otherwise, every variable named \(p\) in this section ranges over the set of all primes.
- \(x / y := \left\lfloor\frac{x}{y}\right\rfloor\)
- \(\operatorname{isprime}(n) := [ |\{d : d \mid n\}| = 2 ]\), which is \(1\) if \(n\) is prime and \(0\) otherwise.
- \(p_{k}\): the \(k\)-th smallest prime (for example, \(p_{1} = 2, p_{2} = 3\)). As a special case, let \(p_{0} = 1\).
- \(\operatorname{lpf}(n) := [1 < n] \min\{p : p \mid n\} + [1 = n]\), the smallest prime factor of \(n\). As a special case, its value is \(1\) when \(n=1\).
- \(F_{\mathrm{prime}}(n) := \sum_{2 \le p \le n} f(p)\)
- \(F_{k}(n) := \sum_{i = 2}^{n} [p_{k} \le \operatorname{lpf}(i)] f(i)\)
Explanation
By the definition of \(F_{k}(n)\), the answer is \(F_{1}(n) + f(1) = F_{1}(n) + 1\).
How do we compute \(F_{k}(n)\)? Enumerating the smallest prime factor of each \(i\) and its exponent gives the recurrence:
The last step relies on the following fact: for the \(c\) with \(p_{i}^{c} \le n < p_{i}^{c + 1}\), we have \(p_{i}^{c + 1} > n \iff n / p_{i}^{c} < p_{i} < p_{i + 1}\), and therefore \(F_{i + 1}\left(n / p_{i}^{c}\right) = 0\).
The boundary condition is \(F_{k}(n) = 0 (p_{k} > n)\).
Suppose all the values \(F_{\mathrm{prime}}(n)\) are already known. There are then two ways to compute all the \(F_{k}(n)\):
- Evaluate the recurrence directly.
- Enumerate \(p\) in decreasing order and apply the transitions. A transition adds a nonzero amount only when \(p^{2} \le n\), so the recurrence can be optimized with suffix sums.
Now consider how to compute \(F_{\mathrm{prime}}{(n)}\).
From the way \(F_{k}(n)\) is computed, the only useful point values of \(F_{\mathrm{prime}}\) are those at the \(O(\sqrt{n})\) points \(1, 2, \dots, \left\lfloor\sqrt{n}\right\rfloor, n / \sqrt{n}, \dots, n / 2, n\).
In general, \(f(p)\) is a low-degree polynomial in \(p\), which can be written as \(f(p) = \sum a_{i} p^{c_{i}}\).
Each \(p^{c_{i}}\) then contributes \(a_{i} \sum_{2 \le p \le n} p^{c_{i}}\) to \(F_{\mathrm{prime}}(n)\).
Treating the contribution of each \(p^{c_{i}}\) separately turns the problem into the following: given \(n, s, g(p) = p^{s}\), compute \(\sum_{p \le m} g(p)\) for every \(m = n / i\).
Note
\(g(p) = p^{s}\) is a completely multiplicative function!
So define \(G_{k}(n) := \sum_{i = 2}^{n} \left[p_{k} < \operatorname{lpf}(i) \lor \operatorname{isprime}(i)\right] g(i)\), the sum of the \(g\) values of the numbers that remain after round \(k\) of the sieve of Eratosthenes.
A composite number \(x \le n\) always has \(\operatorname{lpf}(x) \le \sqrt{x} \le \sqrt{n}\). Let \(p_{\ell(n)}\) be the largest prime not exceeding \(\sqrt{n}\); then \(\sum_{2\le p\le n}g(p) = G_{\ell(n)}(n)\), that is, after \(\ell\) rounds of the sieve only primes remain.
The boundary values of \(G\) are clearly \(G_{0}(n) = \sum_{i = 2}^{n} g(i)\). (Remember? We set \(p_{0} = 1\) as a special case.)
For the transition, follow the sieve of Eratosthenes and consider the contribution of each part separately:
- When \(n < p_{k}^{2}\), the value of \(G\) does not change: \(G_{k}(n) = G_{k - 1}(n)\).
- When \(p_{k}^{2} \le n\), every number that is sieved out has the prime factor \(p_{k}\), which contributes \(-g(p_{k}) G_{k - 1}(n / p_{k})\).
- In the second part, since \(p_{k}^{2} \le n \iff p_{k} \le n / p_{k}\), the \(i\) with \(\operatorname{lpf}(i) < p_{k}\) are subtracted as well. They have to be added back, which contributes \(g(p_{k}) G_{k - 1}(p_{k - 1})\).
This gives:
Complexity analysis
For \(F_{k}(n)\), the first method has been proved to run in \(O\left(n^{1 - \epsilon}\right)\) time (see Zhenting Zhu's Chinese national training team paper Some Special Summation Problems for Arithmetic Functions (in Chinese), Section 2.3).
The second method is in essence the second part of the Zhouge sieve. It is also mentioned in Zhizhou Ren's paper Several Methods for Summing Multiplicative Functions (in Chinese), Section 6.5.4, and has been proved to run in \(O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right)\) time.
The computation of \(F_{\mathrm{prime}}(n)\) is in fact implemented in the same way as the first part of the Zhouge sieve.
For each \(m = n / i\), only the transitions over the \(p_{k}\) with \(p_{k}^{2} \le m\) contribute to the running time, which can therefore be estimated as:
As for space, both \(F_{k}\) and \(F_{\mathrm{prime}}\) are only ever evaluated at the points \(n / i\), of which there are \(O(\sqrt{n})\). Storing only these useful values reduces the space complexity to \(O(\sqrt{n})\).
First, one pass over the integer division blocks yields all the useful values; store them in an array \(\text{lis}\) of size \(O(\sqrt{n})\). For a useful value \(v\), let \(\text{id}(v)\) be the index of \(v\) in \(\text{lis}\). Clearly \(\text{id}(v) \le \sqrt{n}\) for every useful value \(v\).
Then treat the useful values that are at most \(\sqrt{n}\) and those greater than \(\sqrt{n}\) separately. For a useful value \(v\) that is at most \(\sqrt{n}\), record \(\text{id}(v)\) in an array \(\text{le}\), that is, \(\text{le}_v = \text{id}(v)\). For a useful value \(v\) greater than \(\sqrt{n}\), record \(\text{id}(v)\) in an array \(\text{ge}\); since \(v\) is too large to serve as an index, use \(v' = n / v < \sqrt{n}\) instead, that is, \(\text{ge}_{v'} = \text{id}(v)\).
Two arrays of size \(O(\sqrt{n})\) thus record the \(\text{id}\) of every useful value and answer lookups in \(O(1)\). When computing \(F_{k}\) or \(F_{\mathrm{prime}}\), index by the \(\text{id}\) of a useful value instead of the value itself; this reduces the space complexity to \(O(\sqrt{n})\).
Procedure
For \(F_{k}(n)\), we usually implement the first method: it is easier to write, and when the input size is small it often outperforms the second method.
For \(F_{\mathrm{prime}}(n)\), implement the recurrence directly.
For \(p_{k}^{2} \le n\), you can precompute \(s_{k} := F_{\mathrm{prime}}(p_{k})\) with a linear sieve and use it in place of \(F_{\mathrm{prime}}(p_{k - 1})\) in the recurrence for \(F_{k}\).
Likewise, \(G_{k - 1}(p_{k - 1}) = \sum_{i = 1}^{k - 1} g(p_{i})\) in the recurrence for \(G\) can be precomputed in the same way.
Before computing prefix sums of a multiplicative function \(f\) with the Extended Eratosthenes Sieve, settle the following points:
- how to sieve the first \(\sqrt{n}\) values of \(f\) quickly (usually in linear time);
- the polynomial form of \(f(p)\);
- how to evaluate \(f(p^{c})\) quickly.
Once these are settled, implement the following parts in order:
- sieve the primes in \([1, \sqrt{n}]\) and the first \(\sqrt{n}\) values of \(f\);
- for each term of the polynomial form of \(f(p)\), sieve the corresponding \(G\), then combine them to get all \(O(\sqrt{n})\) useful point values of \(F_{\mathrm{prime}}\);
- implement the recurrence for \(F_{k}\) by recursion and compute \(F_{1}(n)\).
Example problems
Luogu P4213 [Template] Du's Sieve
Compute \(\displaystyle \sum_{i = 1}^{n} \varphi(i)\) and \(\displaystyle \sum_{i = 1}^{n} \mu(i)\).
Solution
For the prefix sums of \(\varphi(i)\), first note that \(f(p) = p - 1\). For the linear term \((p)\) of \(f(p)\), we have \(g(p) = p, G_{0}(n) = \sum_{i = 2}^{n} g(i) = \frac{(n + 2) (n - 1)}{2}\); for the constant term \((-1)\) of \(f(p)\), we have \(g(p) = -1, G_{0}(n) = \sum_{i = 2}^{n} g(i) = -n + 1\). Sieve twice and add the results to get all \(O(\sqrt{n})\) required point values of \(F_{\mathrm{prime}}\).
For the prefix sums of \(\mu(i)\), clearly \(f(p) = -1\), so \(g(p) = -1, G_{0}(n) = \sum_{i = 2}^{n} g(i) = -n + 1\). Sieving directly gives all \(O(\sqrt{n})\) required point values of \(F_{\mathrm{prime}}\).
LOJ 6053 Simple Function
The function \(f(n)\) is given by:
Compute \(\displaystyle \sum_{i = 1}^{n} f(i)\).
Solution
Clearly \(f(p) = p - 1 + 2[p = 2]\). So sieve as for \(\varphi\) and treat \(2\) as a special case.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | |
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Marcythm, Xeonacid, CSPNOIP, Great-designer, StudyingFather, Enter-tainer, 24OI-bot, kenlig, ksyx, Ir1d, iamtwz, Persdre, shuzhouliu, CoelacanthusHex, aofall, Tiphereth-A, SamZhangQingChuan, Revltalize, ZnPdCo, HeRaNO, c-forrest, Enoch-xm, chenyichen0420 (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.