Segmented sieve
= Segmented sieve
= Segmented sieve of Eratosthenes
{synonym}
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$.