Powerful Number Sieve
Definition
The powerful number (PN) sieve is similar to Du's sieve, or rather an extension of it. It computes prefix sums of certain multiplicative functions.
Requirements:
- There is a function \(g\) such that:
- \(g\) is multiplicative.
- Prefix sums of \(g\) are easy to compute.
- \(g(p) = f(p)\) for every prime \(p\).
Suppose we want the prefix sum \(F(n) = \sum_{i=1}^{n} f(i)\) of a multiplicative function \(f\).
Powerful numbers
Definition: Let \(n = \prod_{i=1}^{m} p_{i}^{e_{i}}\) be the prime factorization of a positive integer \(n\). Then \(n\) is a PN if and only if \(\forall 1 \le i \le m, e_{i} > 1\).
Property 1: Every PN can be written in the form \(a^{2}b^{3}\).
Proof: If \(e_i\) is even, merge \(p_{i}^{e_{i}}\) into \(a^{2}\). If \(e_i\) is odd, first merge \(p_{i}^{3}\) into \(b^{3}\), then merge \(p_{i}^{e_{i}-3}\) into \(a^{2}\).
Property 2: There are at most \(O(\sqrt{n})\) PNs up to \(n\).
Proof: Enumerate \(a\) and count the values of \(b\) that fit. The number of PNs is approximately
How do we find all the PNs up to \(n\)? Find all primes up to \(\sqrt{n}\) with a linear sieve, then run a DFS over the exponents of these primes. Since there are at most \(O(\sqrt{n})\) PNs up to \(n\), the search takes at most \(O(\sqrt{n})\) steps.
The PN sieve
First, construct a multiplicative function \(g\) whose prefix sums are easy to compute and which satisfies \(g(p) = f(p)\) for every prime \(p\). Let \(G(n) = \sum_{i=1}^{n} g(i)\).
Next, construct the function \(h = f / g\), where \(/\) denotes division under Dirichlet convolution. By the properties of Dirichlet convolution, \(h\) is also multiplicative, so \(h(1) = 1\). We have \(f = g * h\), where \(*\) denotes Dirichlet convolution.
For a prime \(p\), \(f(p) = g(1)h(p) + g(p)h(1) = h(p) + g(p) \implies h(p) = 0\). Since \(h(p)=0\) and \(h\) is multiplicative, \(h(n) = 0\) for every \(n\) that is not a PN. In other words, \(h\) takes useful values only at PNs.
Now \(f = g * h\) gives
Find all the PNs in \(O(\sqrt{n})\) time and compute all the useful values of \(h\). For this it suffices to compute the values \(h(p^c)\): every useful value of \(h\) then follows because \(h\) is multiplicative. Finally, for each useful value \(d\), compute \(h(d)G\left(\left\lfloor \dfrac{n}{d} \right\rfloor\right)\); the sum of these terms is \(F(n)\).
There are two ways to compute \(h(p^c)\). The first is to derive a formula for \(h(p^c)\) that depends only on \(p\) and \(c\), and evaluate it. The second starts from \(f = g * h\), which gives \(f(p^c) = \sum_{i=0}^c g(p^i)h(p^{c-i})\). Rearranging, \(h(p^c) = f(p^c) - \sum_{i=1}^{c}g(p^i)h(p^{c-i})\), so enumerating the primes \(p\) and, for each, the exponents \(c\) yields every \(h(p^c)\).
Procedure
- Construct \(g\).
- Find a fast way to compute \(G\).
- Compute \(h(p^c)\).
- Search for the PNs, accumulating the answer along the way.
- Obtain the result.
Step 3 can be done in three ways: evaluate the formula directly, precompute a table by enumeration, or derive each value on the fly when the search first reaches it.
Properties
We analyze the case where \(h(p^c)\) is computed by the second method. The analysis has two parts: computing \(h(p^c)\), and the search.
For the first part, there are \(O\left(\dfrac{\sqrt{n}}{\log n}\right)\) primes up to \(O(\sqrt{n})\), the exponent \(c\) of each prime \(p\) is at most \(\log n\), and computing \(h(p^c)\) takes a loop of \((c - 1)\) iterations. The first part therefore runs in \(O\left(\dfrac{\sqrt{n}}{\log n} \cdot \log n \cdot \log n\right) = O(\sqrt{n}\log{n})\) time, and this is a loose upper bound. Depending on the problem, further optimizations can lower the time complexity of the first part.
For the search, there are at most \(O(\sqrt{n})\) PNs up to \(n\), so the search takes at most \(O(\sqrt{n})\) steps. The time spent on each PN depends on how \(G\) is computed. For example, if computing \(G\left(\left\lfloor \dfrac{n}{d}\right\rfloor\right)\) takes \(O(1)\) time, the second part runs in \(O(\sqrt{n})\).
In particular, if \(G\left(\left\lfloor \dfrac{n}{d}\right\rfloor\right)\) is computed with Du's sieve, the time complexity of the second part is that of Du's sieve, namely \(O(n^{\frac{2}{3}})\). The reason is this. Compute \(G(n)\) once beforehand, using the linear sieve optimization and storing the larger values in a data structure with fast random access (such as std::map and std::unordered_map in C++). Then every \(G\left(\left\lfloor \dfrac{n}{d}\right\rfloor\right)\) used during Du's sieve is already stored, either by the linear sieve or in the std::map. You can check this directly with a program.
The bottleneck of the space complexity is storing \(h(p^c)\). With a two-dimensional array \(a\) in which \(a_{i,j}\) holds the value of \(h(p_i^j)\), the space complexity is \(O\left(\dfrac{\sqrt{n}}{\log n} \cdot \log n\right) = O(\sqrt{n})\).
Example problems
Luogu P5325 [Template] Min_25 Sieve
Problem statement: Given the multiplicative function \(f(p^k) = p^k(p^k-1)\), compute \(\sum_{i=1}^{n} f(i)\).
Clearly \(f(p) = p(p-1) = \operatorname{id}(p)\varphi(p)\), so construct \(g(n) = \operatorname{id}(n)\varphi(n)\).
Compute \(G(n)\) with Du's sieve: \((\operatorname{id}\cdot \varphi) * \operatorname{id} = \operatorname{id}_2\) gives \(G(n)= \sum_{i=1}^{n} i^2 - \sum_{d=2}^{n} d \cdot G\left(\left\lfloor \dfrac{n}{d} \right\rfloor\right)\).
The values of \(h(p^k)\) can then be computed by enumeration; we do not go over that method again.
In this problem you can also derive a formula for \(h(p^k)\) that depends only on \(p\) and \(k\), as follows:
Together with \(h(p) = 0\), summing these equations over the exponent gives \(h(p^k) = (k-1)(p-1)p^k\).
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 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 | |
LOJ #6053 Simple Function
The function \(f(n)\) is given by:
Clearly:
Construct \(g\) as
It is easy to verify that \(g(p) = f(p)\) and that \(g\) is multiplicative.
Now compute \(G(n)\).
Let \(S_1(n) = \sum_{i=1}^{n} \varphi(i)\) and \(S_2(n) = \sum_{i=1}^{n} \varphi(2i)\). Then \(G(n) = S_1(n) + 2S_2\left(\left\lfloor \dfrac{n}{2} \right\rfloor\right)\).
When \(2 \mid n\),
When \(2 \nmid n\),
In both cases, \(S_2(n) = S_1(n) + S_2\left(\left\lfloor \dfrac{n}{2} \right\rfloor\right)\).
Compute \(S_1\) with Du's sieve and \(S_2\) directly from this formula. This gives \(G\) as well.
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 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | |
Practice problems
References
- wallbreaker5th - A Brief Explanation of the Powerful Number Sieve (in Chinese)
- command_block - Du's Sieve (+ Bell Series + Powerful Number) (in Chinese)
This page is an unofficial English translation of the original OI Wiki page (revision 5a3c3d0d), 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: Great-designer, StudyingFather, Xeonacid, Enter-tainer, 24OI-bot, kenlig, ksyx, Ir1d, xyf007, Marcythm, lrherqwq, iamtwz, Tiphereth-A, LaDeXX (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.