show/hide this revision's text 2 typos

The other answers have covered the right strategies, but here are a few additional comments.

On an idealized computer with an unbounded amount of memory, the cost of sieving $[n_1,n_2]$ for the prime $p$ is $C_1(n_2-n_1)/p$ for some constant $C_1$, the average cost of a memory read & write operation. Therefore, the cost of sieving $[n_1,n_2]$ for all primes up to some bound $B$ is $$C_1 (n_2 - n_1) \sum_{p\leq B} \frac{1}{p} = (n_2 - n_1) (C_1 \log \log B + O(1)),$$ by Merten's the 2nd Mertens Theorem. The numbers in $[n_1,n_2]$ that remain after sieving is approximately $$(n_2-n_1)\prod_{p \leq B} \left(1-\frac{1}{p}\right) = (n_2 - n_1) \frac{e^{-\gamma}}{\log B},$$ by Merten's the 3rd Mertens Theorem. Therefore, the time for testing the remaining numbers for primality is about $$C_2(n_2-n_1) \frac{e^{-\gamma}}{\log B},$$ where $C_2$ is the average cost of a single primality test. The optimal sieving bound $B$ is then approximately $\exp(e^{-\gamma} C_2/C_1)$.

The "constants" $C_1$ and $C_2$ are best determined empirically. In reality, the constant $C_1$ depends heavily on the length of the interval $[n_1,n_2]$ while the constant $C_2$ depends mostly on the size of $n_2$. The constant $C_2$ should vary smoothly with $n_2$, but there will be sharp increases in $C_1$ when the cache size is exceeded and a still larger increase if disk swaps are necessary. Here is a trick that will help you fit longer intervals into the cache, especially if you have multiple processors available. The cost of sieving is higher for small primes, to save some of this time, break the interval into arithmetic progressions $a + Mx$, where $\gcd(a,M) = 1$ and $M = 2\cdot 3 \cdots p_i$ is the product of the first $i$ primes. Each such progression can be sieved independently, possibly on different processors. Essentially, we're breaking the interval into $\phi(M) = (2-1)(3-1)\cdots(p_i-1)$ different progressions which each require $(n_2-n_1)/M$ bits to store in memory while the total sieving and testing times remains about the same. I have some C code that implements this strategy with $M = 2\cdot 3 \cdots 29$ if you're interested.
show/hide this revision's text 1 [made Community Wiki]

The other answers have covered the right strategies, but here are a few additional comments.

On an idealized computer with an unbounded amount of memory, the cost of sieving $[n_1,n_2]$ for the prime $p$ is $C_1(n_2-n_1)/p$ for some constant $C_1$, the average cost of a memory read & write operation. Therefore, the cost of sieving $[n_1,n_2]$ for all primes up to some bound $B$ is $$C_1 (n_2 - n_1) \sum_{p\leq B} \frac{1}{p} = (n_2 - n_1) (C_1 \log \log B + O(1)),$$ by Merten's 2nd Theorem. The numbers in $[n_1,n_2]$ that remain after sieving is approximately $$(n_2-n_1)\prod_{p \leq B} \left(1-\frac{1}{p}\right) = (n_2 - n_1) \frac{e^{-\gamma}}{\log B},$$ by Merten's 3rd Theorem. Therefore, the time for testing the remaining numbers for primality is about $$C_2(n_2-n_1) \frac{e^{-\gamma}}{\log B},$$ where $C_2$ is the average cost of a single primality test. The optimal sieving bound $B$ is then approximately $\exp(e^{-\gamma} C_2/C_1)$.

The "constants" $C_1$ and $C_2$ are best determined empirically. In reality, the constant $C_1$ depends heavily on the length of the interval $[n_1,n_2]$ while the constant $C_2$ depends mostly on the size of $n_2$. The constant $C_2$ should vary smoothly with $n_2$, but there will be sharp increases in $C_1$ when the cache size is exceeded and a still larger increase if disk swaps are necessary. Here is a trick that will help you fit longer intervals into the cache, especially if you have multiple processors available. The cost of sieving is higher for small primes, to save some of this time, break the interval into arithmetic progressions $a + Mx$, where $\gcd(a,M) = 1$ and $M = 2\cdot 3 \cdots p_i$ is the product of the first $i$ primes. Each such progression can be sieved independently, possibly on different processors. Essentially, we're breaking the interval into $\phi(M) = (2-1)(3-1)\cdots(p_i-1)$ different progressions which each require $(n_2-n_1)/M$ bits to store in memory while the total sieving and testing times remains about the same. I have some C code that implements this strategy with $M = 2\cdot 3 \cdots 29$ if you're interested.