MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

This was originally a comment on TonyK's answer, but it was too large to submit as a comment so I'm putting it here. I thought the numbers might have value to some.

Let's say that it takes $b^{\lg 6}/10^{10}$ seconds to test a $b$-bit number with the M-R test and $b^{\lg 24}/10^{13}$ seconds to prove primality with ECPP. Testing a range up to $n_2=2^b$ with M-R + ECPP would take about $$\left(n_2-n_1\right)\left(\frac{b^{\lg 6}}{10^{10}}+\frac{b^{\lg 24}}{10^{13}\ln n_2}\right)=\left(n_2-n_1\right)\left(\frac{b^{\lg 6}}{10^{10}}+\frac{b^{\lg 12}}{10^{13}\ln2}\right)$$ seconds. For $n_2-n_1=2^{20}$ and $n_2$ large, this is about $1.5(\lg n_2)^{\lg12}/10^7$ seconds.

On the other hand, suppose sieving $n_1$ to $n_2$ takes $\sqrt{n_2}/10^6+(n_2-n_1)/10^{8.5}$ seconds. For $n_2-n_1=2^{20}$ and $n_2$ large, this is about $\sqrt{n_2}$ seconds.

Equating the two suggests that, for intervals about a million wide, testing each member is superior to sieving beyond about $n_2>8\cdot10^8$. Only about 12 kB of memory are needed to store all the primes up to the square root of that limit, so the fourth power trick doesn't seem viable here at all -- by the time you run out of primary memory you shouldn't be sieving at all.