title: How does segmentation improve the running time of Sieve of Eratosthenes?
body: <p>I came across a segmented implementation of sieve of Eratosthenes which promises to run many times faster than the conventional version.
  Can someone please explain how segmentation improves the running time?
  Note that I want to find prime numbers in <strong>[1,b]</strong>.</p>
  <p>It works on this idea: (for finding prime numbers till 10^9)</p>
  <blockquote>
  <ul>
  <li><p>We first generate the sieving primes below sqrt(10^9) which are needed to cross-off multiples. Then we start crossing-off the multiples of the first prime 2 until we reach a multiple of 2 &gt;= segment_size, if this happens we calculate the index of that multiple in the next segment using (multiple - segment_size) and store it in a separate array (next[]). We then cross-off the multiples of the next sieving primes using the same procedure. Once we have crossed-off the multiples of all sieving primes in the first segment we iterate over the sieve array and print out (or count) the primes.</p>
  </li>
  <li><p>In order to sieve the next segment we reset the sieve array and we increment the lower offset by segment_size. Then we start crossing-off multiples again, for each sieving prime we retrieve the sieve index from the next array and we start crossing-off multiples from there on...</p>
  </li>
  </ul>
  </blockquote>