SPOJ Problem: Prime Generator

I guess I'm taking a break from USACO training and I'm now starting SPOJ.

Problem is here: http://www.spoj.com/problems/PRIME1/

The problem statement is pretty straightforward and easy to understand.
The difficult part is getting the solution to run in time.

We have that m,n<=10^9, and n-m<=10^5. Thus, simply generating a sieve from 1 - 10^9, and then printing the primes between m and n will not work. Neither will the primality test method for the ~10^5 numbers between m and n.

What we need is a segmented sieve. First, let's see how the sieve of Eratosthenes works. If we wanted to find the primes between 1 and 100, all we need to do is initialize a boolean array of size 100 and take the primes 2,3,5,7 and mark all multiples of those primes to be composite. Why don't we need to consider the multiples of primes 11 and greater? Consider the following argument:

The smallest number that does not have a prime factor in the set {2,3,5,7} is 11*11= 121.

This is relatively easy to see, and 121>100. It follows that if we want to perform a sieve up to N, then we only need to consider the primes <= sqrt(N).

We can just shift our focus to a segment (m,n) now. First, we precompute the primes from 1 to sqrt(10^9) using a normal sieve (there are only about 3500 of them). Next we initialize a boolean array of size n-m+1, where the ith index represents whether m+i is prime or not. The "interesting" multiples of each prime are given by: (ceil(m/p)+k)*p where 0<=k<=n.

Using integer division and loops for each prime p:

for(int j =(m+p-1)/p; j*p<=n; j++)
     if(j!=1)
          sieve[j*p-m]=false;

This raises a puzzling question- What is the runtime complexity? We have our loop through the primes < sqrt(10^9) and then we have our loop to mark the multiples of these primes as composite.
We have something that looks like this: sum(10^5/p) for all primes p < sqrt(10^9). Taking out the 10^5 we get:
10^5(1/2+1/3+1/5+...+ 1/~3500th prime) = ~10^5*(ln(ln(3500))+.26) by the harmonic series for primes approximation. This gives ~250,000 iterations, and since there are 10 test cases 250000*10=2.5*10^6, well under the time limit.