Untitled

$\newcommand{\ceil}[1]{{\left\lceil{#1}\right\rceil}}$ $\newcommand{\floor}[1]{{\left\lfloor{#1}\right\rfloor}}$ $\newcommand{\prob}[1]{\Pr\paren{#1}}$ $\newcommand{\card}[1]{|#1|}$ $\newcommand{\paren}[1]{\left ( #1 \right )}$ $\newcommand{\Paren}[1]{\Big(#1\Big)}$ $\newcommand{\bracket}[1]{\left [ #1 \right ]}$ $\newcommand{\var}[1]{\textnormal{Var}\bracket{#1}}$ $\newcommand{\curly}[1]{\left{ #1 \right}}$ $\newcommand{\poly}{\mbox{\rm poly}}$ $\newcommand{\eps}{\varepsilon}$ $\newcommand{\inner}[2]{\langle #1,,,#2 \rangle}$ $\newcommand{\norm}[1]{ \lVert #1 \rVert}$ $\newcommand{\supp}[1]{\ensuremath{\textnormal{supp}}(#1)}$ $\renewcommand{\leq}{\leqslant}$ $\renewcommand{\geq}{\geqslant}$ $\newcommand{\IR}{\mathbb{R}}$ $\newcommand{\IN}{\mathbb{N}}$ $\newcommand{\backforth}{\leftrightarrow}$

const int N = 1e6 + 9;
int spf[N];
vector<int> pr;

void linear_sieve() {
  pr.reserve(N);
  for (int i = 2; i < N; i++) {
    if (spf[i] == 0) {
      spf[i] = i, pr.push_back(i);
    }
    for (int j = 0; i * pr[j] < N; j++) {
      int p = pr[j];      
      spf[i * p] = p;
      if (i % p == 0) break;
    }
  }
}

We want to show that the above algorithm works in $O(N)$.

Proof. Let $Q(x)$ be the number of iterations of the inner loop over $j$ when $i = x$.

We want to show that

$$\sum_{x = 2}^N Q(x) \leq 2N.$$

Observe that each iteration of the inner loop over $j$ makes an assignment of the array spf. In other words, if we let $S(x)$ to be the set of all those that are assigned in spf when $i = x$, then $Q(x) = \card{S(x)}$.

Let

$$S^{-1}(y) = \curly{x:y \in S(x)}.$$

So,

$$\begin{align*} \sum_{x = 2}^N Q(x) &= \sum_{x = 2}^N |S(x)| \ &= \sum_{x = 2}^N \sum_{y \in S(x)} 1 \ &= \sum_{y = 2}^N \sum_{x \in S^{-1}(y)} 1 \ &= \sum_{y = 2}^N |S^{-1}(y)| \end{align*}$$

We shall show that $|S^{-1}(y)| = 1$ for every $2 \leq y \leq N$, giving us the conclusion.

To proceed, we show the following claim.

---

Claim 1. Fix an outer iteration $i$. In every iteration inner iteration (over $j$) , the lowest prime factor of $p \cdot i$ is $p$.

Denote by the lowest prime factor of $a \geq 2$ by $f(a)$. Observe that since $p$ is prime, then

$$f(p \cdot i) = \min(p, f(i)).$$

Now, note that we iterate over primes in ascending order, and break when $p = f(i)$.

In other words, over inner iterations, $p \leq f(i)$. In other words, $f(p \cdot i) = p$, as desired. $\Box$

---

Suppose $y \geq 2$ is not prime. Let $q$ be the smallest prime divisor of $y$. Write $y = qz$. Note that $z > 1$ becausee $y > q$.

We note that $q \leq f(z)$, for otherwise $f(z)$ will be a prime less than $q$, contradicting minimality of $q$.

This implies that $z \in S^{-1}(y)$. This shows that the condition spf[i] == 0 is false when $i = y$, because $z < y$ assigned the value of spf[y].

This observation, combined with the previous claim (which says that the only one who can assign spf[y] is $z$), shows that $S^{-1}(y) = \curly{z}$.

If $y$ is prime, we note that $y \notin S(z)$ for any $z < y$. For otherwise, $y = qz \geq 2q$ for some prime $q$ (since $z > 1$), which contradicts primality of $y$.

Thus, the condition spf[i] == 0 is true when $i = y$, making $y \in S^{-1}(y)$. Moreover, $y \notin S(z)$ for any $z > y$, since clearly for any $k \geq 2$ and any $m \in S(k)$, we have to have $m \geq k$ (trivial).

This shows that $S^{-1}(y) = \curly{y}$ which concludes the proof. $\Box$.