You can get away with storing $2n_2^{1/4}$ n_2^{1/4}$bits for the sieving data. Generate the first primes$<= n_2^{1/4}$primes, and use them to generate the primes in successive intervals of length$n_2^{1/4}$dynamically, up to$n_2^{1/2}$. The primes thus generated can be used to generate the primes in the interval$[n_1,n_2]$. 1 [made Community Wiki] You can get away with storing$2n_2^{1/4}$bits for the sieving data. Generate the first$n_2^{1/4}$primes, and use them to generate the primes in successive intervals of length$n_2^{1/4}$dynamically, up to$n_2^{1/2}$. The primes thus generated can be used to generate the primes in the interval$[n_1,n_2]\$.