Linear sieve

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 \mathrm{spf}(i)$. Each composite $m$ has a unique representation $m=\mathrm{spf}(m)(m/\mathrm{spf}(m))$ admitted by this rule, giving $O(N)$ arithmetic updates up to $N$.