Optimization on Sieve of Eratosthenes using vector<bool>

Question

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<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= 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 <iostream>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;

int main() {

    ios_base::sync_with_stdio(false);

    int t = 0;
    cin >> t;

    while (t--) {
        ll first = 0, n = 0;
        cin >> first >> n;
        vector<bool> primes(n+1, 0);

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

    return 0;
}

Answer 1

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:

1. Read all test cases first (into a vector for example).
2. Find the maximum n of all the test cases.
3. Use your sieve once to find all primes up to the maximum number.
4. 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 <= sqrt(n); ++i) {

You could instead do:

     for (ll i = 2, sqrt_n = sqrt(n); i <= 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) <= n; ++j) {
                primes[i*j] = 1;
            }

Could be written more optimally as:

            for (ll j = i*i, dj = i+i; j <= 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 <= n; ++i) {
        if (primes[i] == 0 && i >= first) {
            cout << i << '\n';
        }
    }

You should just start the loop at first:

    for (ll i = first; i <= n; ++i) {
        if (primes[i] == 0) {
            cout << i << '\n';
        }
    }

Answer 2

• for (ll j = 2; (i*j) <= n; ++j) : you need not start j from 2, start it from i*i, this is because you would have already checked the combination 2 and i before when i was 2.
• I am not sure if multiplication is costlier than addition, you could refactor i*j in second loop to use addition.
• Instead of finding primes for each input range separately, you could take all inputs at once and calculate for the highest number, and sort out the outputs later, so basically find primes once and not multiple times.

Answer 3

The answers given so far address some inconsequential inefficiencies but they miss the big picture, which is that the SPOJ puzzle in question is designed such that pundits need to invent windowed sieving in order to solve it.

In C/C++ you can actually get away with writing a blazingly fast full sieve and thus solve the problem with superior firepower instead of smarts (2 seconds for sieving up to 2^32-1 on a single core, vs. 15 to 30 seconds for a simple straightforward sieve without all the bells and whistles), but in most other languages that's not an option because you'll get hit with a timeout.

Hence the key is to do only the work requested, which is to sieve the given range (and not all numbers less than the upper end of the range). In order to do that it's also necessary to sieve the small handful of primes up to the square root of the upper limit of the range, but that's peanuts. The whole thing takes only a few milliseconds, even for the most simple-minded implementation using a non-optimising compiler.

Clarification: consider a test case of maximal size at the upper end of the possible range, with m = 999900000, n = 100000000. There are only 100001 numbers in that range but a simple sieve cannot give answers about the range between m and n without processing everything before m as well. This means sieving 10^9 numbers instead of 10^5, an overkill of four orders of magnitude. For smaller ranges the overkill ratio gets even worse.

On the other hand, a windowed/segmented sieve only needs to process the potential prime factors up to sqrt(max(n)) and the actual input ranges. The potential factors up to sqrt(10^9) = 31622 need to be sieved only once, which reduces the number of required operations in the worst-case example above from 10^9 to 10^5 + peanuts, and for the general case to (combined input size + peanuts).

Sieving a range of numbers between m and n involves iterating over all primes (potential factors) up to sqrt(n); for each small prime p, compute the start offset within the window using a bit of modulo arithmetic, then start crossing off numbers as usual (with stride p for odds-only sieves, or 2 * p for 'full' sieves that also hold even numbers).

More detail - including C++ code for a segmented sieve function and a link to various compilable test programs - is given in an answer to the same question elsewhere. The code shown there is for segmented sieving up to 2^64-1, meaning it can be simplified a lot for use in the SPOJ problem.

Using vector<bool> is actually a pessimisation because of the bit references bandied about under the hood. But who cares whether your code is only a hundred times as fast as necessary, instead of a thousand times as fast? As long as the code is fast enough, the only things that count are simplicity and clarity.