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

Правка en2, от dimss, 2023-07-11 08:20:12

There is such an implementation of the sieve of Eratosthenes:

usual

Then replace the second line with bitset used;

bitset

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

linear

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский dimss 2023-07-11 08:20:12 3
en1 Английский dimss 2023-06-30 10:01:47 2238 Initial revision (published)