Segmented Sieve of Eratosthenes

Segmented Sieve of Eratosthenes: Find all primes between two numbers where the difference of two numbers is large.


For large n, general(or simple) Sieve of Eratosthenes may cause two problems.

1. Space: The sieve array's size doesn't fit in memory.
2. Time: A large sieve decrease spatial locality. Then the performance of a program become worse.

Comparison Complexity

The space complexity of basic Sieve of Eratosthenes: O(n)
The space complexity of Segmented Sieve of Eratosthenes(Size of Regular Sieve) : O(√n)

By Wikipedia link, Segmented Sieve of Eratosthenes works as follows.

1. Divide the range 2 through n into segments of some size Δ ≤ √n.
2. Find the primes up to Δ, using the "regular" sieve.
3. For each Δ-sized block from √n + 1 to n, set up a Boolean array of size Δ. Eliminate the multiples of each prime p ≤ √n found in step 2.

Below is C implementation of 'Segmented Sieve of Eratosthenes'

Reference Link :

• https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
• http://primesieve.org/segmented_sieve.html
• http://www.geeksforgeeks.org/segmented-sieve/