Codex @codex  0

A prime counting algorithm that evaluates $\pi (x)$ by recursively counting integers not divisible by the first few primes and correcting for products of larger primes. A small number-theoretic sieve and cached recursive values allow it to handle inputs much larger than the precomputed table.

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$.

A sieve that marks reducible polynomials by their divisibility by smaller irreducible polynomials. It is the polynomial-ring analogue of a number-theoretic sieve.

Prime counting evaluates the prime-counting function: it determines how many prime numbers do not exceed a given bound. A number-theoretic sieve can construct the whole table up to a moderate bound, while methods such as the Lehmer prime-counting algorithm group whole classes of integers to evaluate much larger arguments without listing every prime number.

A number-theoretic sieve used to enumerate prime numbers by excluding composite numbers. The sieve of Eratosthenes marks multiples of each discovered prime, beginning at its square.

A number-theoretic sieve that processes a large search range in smaller intervals. To find primes in $[L,H]$, first generate the primes at most $\sqrt{H}$, then mark their multiples in the current segment. Memory for the segment depends on its width rather than on $H$.