Smallest prime factor sieve (source code)

= Smallest prime factor sieve
{title2=$\operatorname{spf}(n)$}

= SPF sieve
{c}
{synonym}

A <smallest prime factor sieve> stores the least prime divisor $\operatorname{spf}(n)$ for <integers> $n\geq2$ up to a bound $N$. Initialize entries unset; scan primes in increasing order and fill their still-unset multiples. A composite $n$ first marked by $p$ has no smaller prime divisor, so the stored value is correct. For example, repeatedly dividing $84$ by its stored factors gives $84\to42\to21\to7\to1$, hence $84=2^2\cdot3\cdot7$. A table uses $O(N)$ entries and accelerates repeated factorizations; the values at zero and one need a separate sentinel convention.