El Pop

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer $n$. Instead of testing each number for primality (trial division), it works by marking the multiples of each prime as composite, effectively “sieving” out the non-primes.

How it works

1. Initialize: Create a list of booleans from 0 to n, initially all set to True. Mark 0 and 1 as False because they aren’t prime.
2. Iterate: Start with the first prime, $p = 2$.
3. Mark Multiples: While $p^2 \le n$, mark all multiples of p (starting from $p^2, p^2+p, p^2+2p \dots$) as False.
   • Optimization: We start marking at $p^2$ because any smaller multiple (e.g., 2p, 3p) would have already been marked by a previous, smaller prime.
4. Find Next Prime: Find the next number in the list that is still marked True. This is the next prime. Repeat step 3.
5. Result: All numbers remaining as True are primes.

Practical Implementation (Python)

def sieve_of_eratosthenes(n):
    if n < 2:
        return []
    
    # Initialize the sieve
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    # Sieve process
    for p in range(2, int(n**0.5) + 1):
        if is_prime[p]:
            # Mark multiples of p starting from p*p
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
                
    return [p for p, prime in enumerate(is_prime) if prime]
​
# Example: primes up to 30
print(sieve_of_eratosthenes(30))
# Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]Code language: Python (python)

Complexity Analysis

• Time Complexity: $O$($n$ $\log$ $\log$ $n$). This is nearly linear and significantly faster than checking every number individually.
• Space Complexity: $O(n)$ to store the boolean array.

Trade-offs

• Pros: Extremely fast for finding a range of primes.
• Cons: Memory intensive for very large $n$. If you need to find primes in a very high range (e.g., around $10^{12}$), you should use a Segmented Sieve to reduce the memory footprint by processing the range in smaller blocks.

Segmented Sieve

The Segmented Sieve is a memory-optimization of the Sieve of Eratosthenes. While the basic sieve is fast, its $O(n)$ space complexity is a dealbreaker for large n (e.g., if n = $10^{10}$, you can’t allocate a boolean array of 10 billion elements).

The Segmented Sieve solves this by dividing the range $[0, n]$ into small, manageable segments and sieving them one by one.

The Logic

1. Pre-compute Base Primes: Calculate all primes up to $\sqrt{n}$ using the standard Sieve of Eratosthenes. Store these in a list.
2. Divide into Segments: Split the remaining range [ $\sqrt{n}$, $n$ ] into segments of a fixed size $\Delta$ (usually chosen to be $\approx$ $\sqrt{n}$ or the size of your CPU’s L1/L2 cache).
3. Sieve Each Segment: For each segment:
   • Create a small boolean array of size $\Delta$.
   • For every pre-computed base prime p, find the first multiple of $p$ that falls within the current segment.
   • Mark all multiples of p in that segment as composite.
   • After processing all base primes, the remaining True values in the segment are the primes for that range.
4. Discard and Move On: Once a segment is processed, you save the primes and discard the boolean array, reusing that memory for the next segment.

Why this is better (The Trade-offs)

• Memory Efficiency: Space complexity drops from$O(n)$ to $O(\sqrt{n})$. You only need to store the base primes and one small segment array at a time.
• Cache Friendliness: Because the segment array is small, it fits entirely in the CPU’s cache. This prevents “cache misses” (hitting slow RAM), making it practically faster than the basic sieve for large ranges.

Practical Implementation

import math
​
def simple_sieve(limit):
    """Standard sieve to get base primes up to sqrt(n)"""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(limit**0.5) + 1):
        if is_prime[p]:
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
    return [p for p, prime in enumerate(is_prime) if prime]
​
def segmented_sieve(n):
    limit = int(math.sqrt(n))
    base_primes = simple_sieve(limit)
    
    # Start with the base primes
    primes = list(base_primes)
    
    # Segment size (chosen to be roughly sqrt(n))
    segment_size = limit
    low = limit + 1
    high = low + segment_size
    
    while low <= n:
        if high > n:
            high = n
            
        # Boolean array for the current segment [low, high]
        # is_prime[i] represents number (low + i)
        is_prime = [True] * (high - low + 1)
        
        for p in base_primes:
            # Find the first multiple of p in [low, high]
            # start = ceil(low / p) * p
            start = (low + p - 1) // p * p
            
            # Ensure we start marking from the first multiple >= low
            # and that we don't mark the prime itself as composite
            j = max(start, p * p)
            
            while j <= high:
                is_prime[j - low] = False
                j += p
        
        # Collect primes from this segment
        for i in range(len(is_prime)):
            if is_prime[i]:
                primes.append(low + i)
        
        # Move to next segment
        low += segment_size
        high += segment_size
        
    return primes
​
# Example: Primes up to 100
print(segmented_sieve(100))Code language: Python (python)

Summary Comparison

Feature	Basic Sieve	Segmented Sieve
Time Complexity	$O$($n$ $log$ $log$ $n$)	$O$($n$ $log$ $log$ $n$)
Space Complexity	$O(n)$	$O(\sqrt{n})$
RAM Usage	Massive for large n	Constant/Small
CPU Cache	Poor (random access over large array)	Excellent (localized access)
Best Use Case	Small n (up to $\sim 10^7$)	Large n or range-based queries