Linear sieve
= Linear sieve
= Euler’s linear sieve
{c}
{synonym}
A <number-theoretic sieve> that visits each <composite number> exactly once, through its <smallest prime factor>. Keep a growing list of <prime numbers>; for each $i$, generate $ip$ only for stored primes $p\le\operatorname{spf}(i)$. Each composite $m$ has a unique representation $m=\operatorname{spf}(m)(m/\operatorname{spf}(m))$ admitted by this rule, giving $O(N)$ arithmetic updates up to $N$.