How to speed up the sieve of Eratosthenes by 1.5 times with one line

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

There is such an implementation of the sieve of Eratosthenes:

usual

const int N = 1e8;

bool used[N];

void solve() {
    ll sum = 0;
    for (int i = 2; i < N; i++) {
        if (!used[i]) {
            sum += i;
            for (int j = min((ll)INT32_MAX, i * 1ll * i); j < N; j += i)
                used[j] = true;
        }
    }
    cout << sum << "\n";
}

Then replace the second line with bitset used;

bitset

const int N = 1e8;

bitset<N> used;

void solve() {
    ll sum = 0;
    for (int i = 2; i < N; i++) {
        if (!used[i]) {
            sum += i;
            for (int j = min((ll)INT32_MAX, i * 1ll * i); j < N; j += i)
                used[j] = true;
        }
    }
    cout << sum << "\n";
}

For comparison, let 's take another linear sieve of Eratosthenes.

linear

const int N = 1e8;

int le[N], primes[N / 10];

void solve() {
    ll sum = 0;
    int m = 0;
    for (int i = 2; i < N; i++) {
        if (!le[i]) {
            sum += i;
            primes[m++] = i;
            le[i] = i;
        }
        for (int j = 0; j < m && primes[j] <= le[i] && primes[j] * i < N; j++)
            le[primes[j] * i] = primes[j];
    }
    cout << sum << "\n";
}

Running time table on compiler GNU G++20 11.2.0 (64 bit, winlibs) with #pragma GCC optimize("O3") in all three solutions.

\begin{array}{|c|c|c|c|} \hline N & usual & linear & bitset \cr \hline 2e7 & 202ms & 140ms & 78ms \cr \hline 5e7 & 467ms & 374ms & 249ms \cr \hline 1e8 & 1138ms & 732ms & 686ms \cr \hline 2e8 & 2308ms & ML & 1669ms \cr \hline \end{array}

I guess it's because of the cache. The data takes up 8 times less memory and is cached better. The more cache there is on the computer, the more noticeable the acceleration. For example, I have a 3-fold acceleration on $$$N = 1e8$$$ compared to a conventional sieve.

Unfortunately, this is useless in practice, because almost always in the sieve we want to get some more information.