Introduction

For most practical values of N, the fastest general-purpose way to list all primes below N is a sieve, not repeated primality testing. The exact best sieve depends on scale: an optimized Sieve of Eratosthenes is great for moderate ranges, while a segmented sieve becomes the better practical choice once memory locality matters.

Why Trial Division Is Not the Fastest

Testing every number individually with trial division is simple, but it wastes work. If you test each odd candidate up to its square root, the total cost grows much faster than a sieve.

That is why the interview or practical answer is usually:

• do not test one number at a time
• mark composites in bulk

This is exactly what sieves are good at.

The Standard Answer: Sieve of Eratosthenes

The classic sieve marks multiples of each prime starting from p * p:

1def sieve(n):
2    if n < 2:
3        return []
4
5    is_prime = [True] * n
6    is_prime[0] = is_prime[1] = False
7
8    p = 2
9    while p * p < n:
10        if is_prime[p]:
11            for multiple in range(p * p, n, 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))

This is already very fast and has time complexity about O(n log log n) with O(n) memory.

For many real applications, this is the right answer.

An Important Practical Optimization: Skip Even Numbers

You can cut both work and memory substantially by storing only odd candidates:

1def odd_only_sieve(n):
2    if n < 2:
3        return []
4    if n == 2:
5        return [2]
6
7    size = (n - 1) // 2
8    is_prime = [True] * size
9
10    limit = int(n ** 0.5)
11    for i in range((limit - 1) // 2 + 1):
12        if is_prime[i]:
13            p = 2 * i + 3
14            start = (p * p - 3) // 2
15            for j in range(start, size, p):
16                is_prime[j] = False
17
18    primes = [2]
19    primes.extend(2 * i + 3 for i, flag in enumerate(is_prime) if flag)
20    return [p for p in primes if p < n]
21
22
23print(odd_only_sieve(30))

This is still conceptually the Sieve of Eratosthenes, just implemented more efficiently.

When N Gets Large: Use a Segmented Sieve

If N is very large, a full O(n) boolean array can become the bottleneck. That is where a segmented sieve helps.

The idea is:

1. generate primes up to sqrt(N)
2. process the range [2, N) in manageable blocks
3. mark composites in each block using the small base primes

This improves cache behavior and reduces peak memory usage. It is usually the practical answer when someone asks for the "fastest" method at larger scales.

The segmented version is more implementation work, but it is the next step after the ordinary sieve, not a completely different idea.

What About the Sieve of Atkin

The Sieve of Atkin has better-looking asymptotic discussion in some contexts, but in practice it is often slower or more complex for everyday use. Unless you are doing specialized prime generation work, the ordinary or segmented Eratosthenes sieve is the better engineering choice.

So the realistic hierarchy is often:

• simple sieve for normal use
• odd-only sieve for better constants
• segmented sieve for huge ranges

That is much more useful than chasing a theoretically fancier algorithm with worse constant factors.

Choose Based on the Goal

Ask what "fastest" means in context:

• fastest to write correctly
• fastest wall-clock time
• fastest under strict memory limits

For a coding interview, an optimized Sieve of Eratosthenes is usually enough. For production prime generation over very large ranges, segmented sieving is the stronger answer.

That distinction matters because the right answer changes with scale.

Common Pitfalls

• Using trial division for every number when the task is to list all primes up to N.
• Forgetting to start crossing off multiples at p * p.
• Storing even numbers even though all even numbers above 2 are composite.
• Assuming the fanciest named sieve is automatically fastest in practice.
• Ignoring memory behavior when N becomes very large.

Summary

• The fastest practical way to list all primes below N is usually a sieve, not repeated primality tests.
• The Sieve of Eratosthenes is the standard general-purpose answer.
• Odd-only representations improve constants significantly.
• For very large N, segmented sieves are usually the practical upgrade.
• "Fastest" depends on both time and memory, so scale matters.