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]$.
|
2 | deleted 4 characters in body | ||
|
|
||||
|
|
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]$. |
||||
