There are 3401 primes below the square root of 109. That's all you need to sieve any segment of numbers below the 109 upper limit.
So, first, sieve a segment from 2 to 31622. Store the resulting 3401 prime integers in an array.
Then for each pair of numbers m <= n, m >= n - 100000
create a temporary array covering the segment from m
to n
inclusive, and sieve it with those primes you've calculated in the first step. You can stop each sieving when a prime's square is above a given n
:
for( i=0; primes[i]*primes[i] <= n; ++i)
{
....