# Optimization on Sieve of Eratosthenes using vector<bool>

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;
}

• Please use meaningful variable names. I think I can guess what t is for, but I really don't want to spend any further time trying to figure out what this code is trying to do. – Pete Becker Nov 29 '15 at 15:28
• @PeteBecker Thanks for the advice! :) and t stands for the number of test cases. – Deepam Sarmah Nov 29 '15 at 17:05
• Don't use vector<bool> it differs significantly from other containers and is optimized for space not speed. Your code will run much quicker by using vector<char> – Martin York Nov 29 '15 at 19:54
• Did nobody mention that the declaration of prime is in the wrong place. By moving it out a level you don't need to re-calculate all the values again and again. – Martin York Nov 29 '15 at 19:58
• Since 2 is a prime. You can start at 3 and increment by 2 for testing (rather than incrementing by 1). – Martin York Nov 29 '15 at 19:59

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


     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';
}
}

• For "Don't use expensive operations in loop iterator", I think it would be better to have sqrt_n inside the init-statement condition of the for statement. That way it is in the narrowest possible scope. Ex: for (ll i = 2, sqrt_n = sqrt(n); i <= sqrt_n; ++i) { ... } – user2296177 Nov 29 '15 at 18:09
• @user2296177 i edited my answer to include your suggestion. – JS1 Nov 29 '15 at 18:56
• @JS1 I have tried all the optimizations that you mentioned but still I get TLE. Here is my code. – Deepam Sarmah Nov 30 '15 at 14:10
• @DeepamSarmah Your print loop is wrong. I'm not sure what you think your print loop is doing but it is printing $O(n^2)$ primes. You need to loop through your test cases and print only the primes within the test ranges. – JS1 Nov 30 '15 at 18:25
• 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.
• (comment added by mistake - deleted. mea culpa) – DarthGizka Dec 3 '15 at 10:59

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.