Introduction

When people talk about sieve optimization, they usually mean making prime generation faster and leaner than the textbook Sieve of Eratosthenes implementation. The big gains come from avoiding unnecessary work: skip even numbers, start crossing out at p * p, and, for large limits, use segmented processing instead of one giant in-memory array.

Start with the Core Sieve Improvement

A naïve sieve marks multiples starting at 2 * p, even though smaller multiples were already handled by earlier primes. A better version starts at p * p.

1def sieve(limit: int) -> list[int]:
2    if limit < 2:
3        return []
4
5    is_prime = [True] * (limit + 1)
6    is_prime[0] = is_prime[1] = False
7
8    p = 2
9    while p * p <= limit:
10        if is_prime[p]:
11            for multiple in range(p * p, limit + 1, p):
12                is_prime[multiple] = False
13        p += 1
14
15    return [i for i, prime in enumerate(is_prime) if prime]
16
17
18print(sieve(30))

Starting at p * p is not a tiny micro-optimization. It removes a large amount of redundant marking.

Skip Even Numbers

After handling 2, every remaining prime candidate is odd. Storing and checking only odd numbers cuts memory roughly in half and reduces loop work.

1def odd_only_sieve(limit: int) -> list[int]:
2    if limit < 2:
3        return []
4    if limit == 2:
5        return [2]
6
7    size = (limit // 2) + 1
8    is_prime = [True] * size
9    is_prime[0] = False  # number 1
10
11    p = 3
12    while p * p <= limit:
13        idx = p // 2
14        if is_prime[idx]:
15            start = p * p
16            step = 2 * p
17            for multiple in range(start, limit + 1, step):
18                is_prime[multiple // 2] = False
19        p += 2
20
21    primes = [2]
22    primes.extend(2 * i + 1 for i in range(1, size) if is_prime[i] and (2 * i + 1) <= limit)
23    return primes
24
25
26print(odd_only_sieve(30))

This version keeps the same mathematical result while wasting less space on values that can never be prime.

Use Segmented Sieve for Large Ranges

For very large limits, the main problem is memory locality. A segmented sieve processes the range in blocks, using smaller working arrays that fit cache better.

The rough approach is:

1. generate primes up to sqrt(limit)
2. process [low, high] blocks
3. mark composites in each block using the base primes

1import math
2
3
4def segmented_count(limit: int, block_size: int = 10000) -> int:
5    base_primes = sieve(int(math.isqrt(limit)))
6    count = 0
7
8    for low in range(2, limit + 1, block_size):
9        high = min(low + block_size - 1, limit)
10        block = [True] * (high - low + 1)
11
12        for p in base_primes:
13            start = max(p * p, ((low + p - 1) // p) * p)
14            for multiple in range(start, high + 1, p):
15                block[multiple - low] = False
16
17        for i, flag in enumerate(block):
18            value = low + i
19            if value >= 2 and flag:
20                count += 1
21
22    return count
23
24
25print(segmented_count(100))

Segmented sieve is the right move when the target range is big enough that one full boolean array becomes wasteful.

Think About Representation

Beyond algorithmic improvements, representation matters:

• Python list[bool] is easy but not memory-optimal
• bitsets are smaller
• cache-friendly arrays often outperform theoretically similar but fragmented structures

In low-level languages, bit-packed storage can be a major win. In higher-level languages, it is worth balancing implementation complexity against actual performance needs.

Benchmark the Right Bottleneck

Not every optimization helps equally for every limit. For smaller ranges, a plain p * p optimization may be enough. For larger ranges, segmented processing may dominate. Benchmark with realistic limits before making the code complicated.

A practical rule:

• small limit: simple sieve
• medium limit: odd-only sieve
• large limit: segmented sieve

The best version depends on your input sizes and memory constraints.

Common Pitfalls

• Starting composite marking at 2 * p repeats work that earlier primes already handled.
• Keeping even numbers in the candidate array wastes memory and iterations.
• Using segmented sieve for tiny inputs can add complexity without meaningful benefit.
• Ignoring cache behavior can make a theoretically good implementation slower in practice.
• Benchmarking only once on a tiny range can lead to the wrong optimization choice for real workloads.

Summary

• Start composite marking at p * p, not 2 * p.
• Skip even numbers after handling prime 2.
• Use segmented sieve when the range is large enough that memory locality matters.
• Choose data representation based on actual performance constraints, not habit.
• Optimize in stages and benchmark against the input sizes you really care about.