Programming Praxis

We examined the Sieve of Eratosthenes for computing prime numbers less than n in our second exercise nearly a year ago. In today’s exercise, we update that algorithm to compute the prime numbers in a range L to R, where the range doesn’t start at zero and is too large to fit in memory all at once. Specifically, we discuss a function that takes parameters L, for the left end of the range, and R, for the right end of the range, and a parameter B that divides R – L; we also assume that the primes less than the square root of R are known. In practice, L and R will be large, maybe 10¹⁶ or 10¹⁸, and B will be somewhat smaller, maybe 10⁸ or 10¹⁰.

We will explain the algorithm by computing the primes in the range 100 to 200, with B = 10; since we don’t look at even numbers, the algorithm will make five passes, each time sieving twenty numbers.

There are six primes less than the square root of 200: 2, 3, 5, 7, 11, and 13; we will ignore 2, since it is even. Associated with each prime P_k is a number we will call Q_k that is the offset within B of the first prime in the current sieving block that is divisible by P_k. For instance, when sieving from 100 to 120, the primes are 3, 5, 7, 11, and 13 and the associated Qs are 2, 2, 2, 10, and 8. Each Q_k can be initialized by computing Q_k = (-1/2 × (L + 1 + P_k)) mod P_k and re-initialized for the next 2B block by computing Q_k = (Q_k – B) mod P_k; for instance, the Qs at the second sieving block from 120 to 140 are 1, 2, 6, 0, and 11.

Within each sieving block, we create an array of booleans (in practice, it is common to use bits) that is initialized to true. Then each prime is sieved in the normal way starting at the Q_k offset. In our example, prime 3 with associated Q = 2 causes us to reset bits 2, 5, and 8 to false. Likewise, prime 5 causes us to reset bits 2 and 7, prime 7 causes us to reset bits 2 and 9, prime 11 has no odd multiples in the current sieving block, and prime 13 causes us to reset bit 8. After sieving, the bits that are still true are 0, 1, 3, 4, and 6, which correspond to primes 101, 103, 107, 109, and 113.

It is instructive to take five minutes to work out the example sieve by hand.

Your task is to write a function that performs a segmented sieve of Eratosthenes as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2