Introduction

When people ask for the most elegant way to generate prime numbers, they usually mean a solution that is both clear and reasonably efficient. For generating all primes up to a limit, the classic answer is the Sieve of Eratosthenes because it is simple to understand and much faster than testing every number independently.

Start with the Sieve of Eratosthenes

The sieve works by assuming every number is prime at first, then crossing out multiples of each prime as you discover it. What remains unmarked at the end are the primes.

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

This prints:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The elegance comes from the fact that every composite number gets ruled out by one of its smaller prime factors. You do not need to keep checking divisibility from scratch for every candidate.

Why It Beats Repeated Trial Division

A straightforward beginner approach is to test each number by dividing it by every smaller number, or at least by every number up to its square root.

That works, but it repeats too much work. The sieve is better when you want all primes up to n because it marks many composite numbers in one pass rather than rediscovering the same divisibility facts over and over.

For one-off primality checks, trial division can still be fine:

1def is_prime(n: int) -> bool:
2    if n < 2:
3        return False
4    if n == 2:
5        return True
6    if n % 2 == 0:
7        return False
8
9    divisor = 3
10    while divisor * divisor <= n:
11        if n % divisor == 0:
12            return False
13        divisor += 2
14
15    return True
16
17
18print([n for n in range(2, 31) if is_prime(n)])

This is readable, but if the task is "generate primes up to a limit," the sieve is usually the better tool.

A Memory-Friendly Generator Approach

Sometimes you do not know the upper bound in advance, or you want a stream of primes rather than a full list. In that case, a generator based on trial division by earlier primes is a nice compromise between elegance and practicality.

1def prime_generator():
2    primes: list[int] = []
3    candidate = 2
4
5    while True:
6        is_prime_candidate = True
7
8        for p in primes:
9            if p * p > candidate:
10                break
11            if candidate % p == 0:
12                is_prime_candidate = False
13                break
14
15        if is_prime_candidate:
16            primes.append(candidate)
17            yield candidate
18
19        candidate += 1 if candidate == 2 else 2
20
21
22gen = prime_generator()
23print([next(gen) for _ in range(10)])

This version is attractive when you want the first few primes on demand without allocating a sieve array up to a fixed maximum.

Choosing the Right Definition of Elegant

Elegant does not always mean shortest code. In algorithm discussions, elegant usually means:

• the idea is easy to explain
• the implementation avoids unnecessary work
• the code is still readable when revisited later

By that standard, the Sieve of Eratosthenes is elegant because the core idea matches the implementation directly. You are literally sieving out composites.

If you only need to check one number at a time, the prime-checking function may feel more elegant because it uses less memory and solves the smaller problem directly.

Common Pitfalls

One common mistake is starting to mark multiples at 2 * p instead of p * p. Values below p * p have already been handled by smaller factors, so starting earlier does extra work for no benefit.

Another mistake is forgetting the edge cases for numbers less than 2. Zero and one are not prime, and that should be explicit in the code.

Developers also sometimes choose a clever-looking one-liner that is hard to read and much slower than a standard sieve. Compact code is not automatically elegant if it hides the algorithm.

Finally, use the right approach for the task. If you need all primes up to a million, repeated trial division is the wrong baseline even if the code looks simple.

Summary

• For generating all primes up to a limit, the Sieve of Eratosthenes is the classic elegant solution.
• Trial division is simpler for checking a single number but less efficient for bulk generation.
• A prime generator is useful when you want primes lazily instead of up to a fixed bound.
• Starting the sieve at p * p avoids unnecessary work.
• Elegant prime-generation code should be readable, correct, and appropriate for the problem size.