Skip to content

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:

\[ \begin{aligned} F_{k}(n) &= \sum_{i = 2}^{n} [p_{k} \le \operatorname{lpf}(i)] f(i) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c} \le n}} f\left(p_{i}^{c}\right) ([c > 1] + F_{i + 1}\left(n / p_{i}^{c}\right)) + \sum_{\substack{k \le i \\ p_{i} \le n}} f(p_{i}) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c} \le n}} f\left(p_{i}^{c}\right) ([c > 1] + F_{i + 1}\left(n / p_{i}^{c}\right)) + F_{\mathrm{prime}}(n) - F_{\mathrm{prime}}(p_{k - 1}) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c + 1} \le n}} \left(f\left(p_{i}^{c}\right) F_{i + 1}\left(n / p_{i}^{c}\right) + f\left(p_{i}^{c + 1}\right)\right) + F_{\mathrm{prime}}(n) - F_{\mathrm{prime}}(p_{k - 1}) \end{aligned} \]

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)\):

  1. Evaluate the recurrence directly.
  2. 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:

  1. When \(n < p_{k}^{2}\), the value of \(G\) does not change: \(G_{k}(n) = G_{k - 1}(n)\).
  2. 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})\).
  3. 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:

\[ G_{k}(n) = G_{k - 1}(n) - \left[p_{k}^{2} \le n\right] g(p_{k}) (G_{k - 1}(n / p_{k}) - G_{k - 1}(p_{k - 1})) \]

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:

\[ \begin{aligned} T(n) &= \sum_{i^{2} \le n} O\left(\pi\left(\sqrt{i}\right)\right) + \sum_{i^{2} \le n} O\left(\pi\left(\sqrt{\frac{n}{i}}\right)\right) \\ &= \sum_{i^{2} \le n} O\left(\frac{\sqrt{i}}{\ln{\sqrt{i}}}\right) + \sum_{i^{2} \le n} O\left(\frac{\sqrt{\frac{n}{i}}}{\ln{\sqrt{\frac{n}{i}}}}\right) \\ &= O\left(\int_{1}^{\sqrt{n}} \frac{\sqrt{\frac{n}{x}}}{\log{\sqrt{\frac{n}{x}}}} \mathrm{d} x\right) \\ &= O\left(\frac{n^{\frac{3}{4}}}{\log{n}}\right) \end{aligned} \]

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:

  1. sieve the primes in \([1, \sqrt{n}]\) and the first \(\sqrt{n}\) values of \(f\);
  2. 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}}\);
  3. 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:

\[ f(n) = \begin{cases} 1 & n = 1 \\ p \operatorname{xor} c & n = p^{c} \\ f(a)f(b) & n = ab \land a \perp b \end{cases} \]

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
/* [LOJ #6053] Simple Function */
#include <cmath>
#include <iostream>

constexpr int MAXS = 200000;  // 2sqrt(n)
constexpr int mod = 1000000007;

template <typename x_t, typename y_t>
void inc(x_t &x, const y_t &y) {
  x += y;
  (mod <= x) && (x -= mod);
}

template <typename x_t, typename y_t>
void dec(x_t &x, const y_t &y) {
  x -= y;
  (x < 0) && (x += mod);
}

template <typename x_t, typename y_t>
int sum(const x_t &x, const y_t &y) {
  return x + y < mod ? x + y : (x + y - mod);
}

template <typename x_t, typename y_t>
int sub(const x_t &x, const y_t &y) {
  return x < y ? x - y + mod : (x - y);
}

template <typename _Tp>
int div2(const _Tp &x) {
  return ((x & 1) ? x + mod : x) >> 1;
}

// everything above keeps values non-negative and reduced modulo mod
template <typename _Tp>
long long sqrll(const _Tp &x) {  // square of x
  return (long long)x * x;
}

int pri[MAXS / 7], lpf[MAXS + 1], spri[MAXS + 1], pcnt;

void sieve(const int &n) {
  for (int i = 2; i <= n; ++i) {
    if (lpf[i] == 0) {  // record the prime
      lpf[i] = ++pcnt;
      pri[lpf[i]] = i;
      spri[pcnt] = sum(spri[pcnt - 1], i);  // prefix sum
    }
    for (int j = 1, v; j <= lpf[i] && (v = i * pri[j]) <= n; ++j) lpf[v] = j;
  }
}

long long global_n;
int lim;
int le[MAXS + 1],  // x <= \sqrt{n}
    ge[MAXS + 1];  // x > \sqrt{n}
#define idx(v) (v <= lim ? le[v] : ge[global_n / v])

int G[MAXS + 1][2], Fprime[MAXS + 1];
long long lis[MAXS + 1];
int cnt;

void init(const long long &n) {
  for (long long i = 1, j, v; i <= n; i = n / j + 1) {
    j = n / i;
    v = j % mod;
    lis[++cnt] = j;
    (j <= lim ? le[j] : ge[global_n / j]) = cnt;
    G[cnt][0] = sub(v, 1ll);
    G[cnt][1] = div2((long long)(v + 2ll) * (v - 1ll) % mod);
  }
}

void calcFprime() {
  for (int k = 1; k <= pcnt; ++k) {
    const int p = pri[k];
    const long long sqrp = sqrll(p);
    for (int i = 1; lis[i] >= sqrp; ++i) {
      const long long v = lis[i] / p;
      const int id = idx(v);
      dec(G[i][0], sub(G[id][0], k - 1));
      dec(G[i][1], (long long)p * sub(G[id][1], spri[k - 1]) % mod);
    }
  }
  /* F_prime = G_1 - G_0 */
  for (int i = 1; i <= cnt; ++i) Fprime[i] = sub(G[i][1], G[i][0]);
}

int f_p(const int &p, const int &c) {
  /* f(p^{c}) = p xor c */
  return p ^ c;
}

int F(const int &k, const long long &n) {
  if (n < pri[k] || n <= 1) return 0;
  const int id = idx(n);
  long long ans = Fprime[id] - (spri[k - 1] - (k - 1));
  if (k == 1) ans += 2;
  for (int i = k; i <= pcnt && sqrll(pri[i]) <= n; ++i) {
    long long pw = pri[i], pw2 = sqrll(pw);
    for (int c = 1; pw2 <= n; ++c, pw = pw2, pw2 *= pri[i])
      ans +=
          ((long long)f_p(pri[i], c) * F(i + 1, n / pw) + f_p(pri[i], c + 1)) %
          mod;
  }
  return ans % mod;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> global_n;
  lim = sqrt(global_n);  // upper bound

  sieve(lim + 1000);  // preprocessing
  init(global_n);
  calcFprime();
  cout << (F(1, global_n) + 1ll + mod) % mod << '\n';

  return 0;
}