Optimization on Sieve of Eratosthenes using vector I am solving this prime generator problem from SPOJ:

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
Input
The input begins with the number t of test cases in a single line (t&lt;=10). In each of the next t lines there are two numbers m and n (1 &lt;= m &lt;= n &lt;= 1000000000, n-m&lt;=100000) separated by a space.
Output
For every test case print all prime numbers p such that m &lt;= p &lt;= n, one number per line, test cases separated by an empty line.


I’m using the Sieve of Eratosthenes. Whenever I submit the following code it gives Time Limit Exceeded. Can anyone please give me some optimizations that can make my code run faster?
#include &lt;iostream&gt;
#include &lt;cmath&gt;
#include &lt;vector&gt;
using namespace std;
using ll = long long;

int main() {

    ios_base::sync_with_stdio(false);

    int t = 0;
    cin &gt;&gt; t;

    while (t--) {
        ll first = 0, n = 0;
        cin &gt;&gt; first &gt;&gt; n;
        vector&lt;bool&gt; primes(n+1, 0);

        for (ll i = 2; i &lt;= sqrt(n); ++i) {
            if (primes[i] == 0) {
                for (ll j = 2; (i*j) &lt;= n; ++j) {
                    primes[i*j] = 1;
                }  
            }
        }
    
        for (ll i = 2; i &lt;= n; ++i) {
            if (primes[i] == 0 &amp;&amp; i &gt;= first) {
                cout &lt;&lt; i &lt;&lt; '\n';
            }
        }
   
    }

    return 0;
}
Repeating work already done
The biggest problem with your solution is that for each test case, you start over from scratch.  This causes you to do up to 10x the work that you need to do.  What you should do instead is:

Read all test cases first (into a vector for example).
Find the maximum n of all the test cases.
Use your sieve once to find all primes up to the maximum number.
Using the vector of primes that you produced with the sieve, solve all test cases.

Don't use expensive operations in loop iterator
Depending on your compiler, this line could be costly:

    for (ll i = 2; i &lt;= sqrt(n); ++i) {


You could instead do:
     for (ll i = 2, sqrt_n = sqrt(n); i &lt;= sqrt_n; ++i) {

to make sure that you don't call sqrt() once per loop iteration.
Sieve loop improvements
This sieve loop:

            for (ll j = 2; (i*j) &lt;= n; ++j) {
                primes[i*j] = 1;
            }


Could be written more optimally as:
            for (ll j = i*i, dj = i+i; j &lt;= n; j += dj) {
                primes[j] = 1;
            }

Notice, the loop starts at i*i instead of 2*i, and it iterates by 2*i instead of by i.  It also avoids multiplication within the main loop.  However, this loop assumes that all even numbers have already been marked from the primes array, so you will have to do that separately when you create the primes array.
Printing loop
The printing loop is not optimal because it starts at 2, even though first may be very large:

    for (ll i = 2; i &lt;= n; ++i) {
        if (primes[i] == 0 &amp;&amp; i &gt;= first) {
            cout &lt;&lt; i &lt;&lt; '\n';
        }
    }


You should just start the loop at first:
    for (ll i = first; i &lt;= n; ++i) {
        if (primes[i] == 0) {
            cout &lt;&lt; i &lt;&lt; '\n';
        }
    }