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).

Let $S=\sqrt{n_1}$. S=\sqrt{n_2}$. If S is bigger than your computer's memory in bits, then you're going to have trouble generating all the primes in that range; if you insist, break the range into pieces that fit into memory, mark off the ones with small divisors, and test the remaining numbers for primality. You want to do as much sieving as possible, so fill maybe half the memory with primes and use those for sieving. If S fits in memory and$n_2-n_1$is not much smaller than S, use a sieve (sieve of Atkin or Eratosthenes). You may need to use a segmented version of the sieve, depending on how large$n_2-n_1$is. If$n_2-n_1$is significantly smaller than S, make a bit array of (segments of?) the range, mark off small divisors, and test the remaining members for primality. 2 added 114 characters in body Let$S=\sqrt{n_1}$. If S is bigger than your computer's memory in bits, then you're going to have trouble generating all the primes in that range; if you insist, break the range into pieces that fit into memory, mark off the ones with small divisors, and test the remaining numbers for primality. You want to do as much sieving as possible, so fill maybe half the memory with primes and use those for sieving. If S fits in memory and$n_2-n_1$is not much smaller than S, use a sieve (sieve of Atkin or Eratosthenes). You may need to use a segmented version of the sieve, depending on how large$n_2-n_1$is. If$n_2-n_1$is significantly smaller than S, make a bit array of (segments of?) the range, mark off small divisors, and test the remaining members for primality. 1 Let$S=\sqrt{n_1}$. If S is bigger than your computer's memory in bits, then you're going to have trouble generating all the primes in that range; if you insist, break the range into pieces that fit into memory, mark off the ones with small divisors, and test the remaining numbers for primality. If S fits in memory and$n_2-n_1$is not much smaller than S, use a sieve (sieve of Atkin or Eratosthenes). You may need to use a segmented version of the sieve, depending on how large$n_2-n_1$is. If$n_2-n_1\$ is significantly smaller than S, make a bit array of (segments of?) the range, mark off small divisors, and test the remaining members for primality.