---

Mastering Prime Numbers: The Ultimate Guide to the Sieve of Eratosthenes in Common Lisp

The Sieve of Eratosthenes is a highly efficient, ancient algorithm for finding all prime numbers up to a specified integer. This definitive guide explores its underlying logic, provides a detailed walkthrough of a robust implementation in Common Lisp, and examines its performance characteristics for modern computing challenges.

You’ve done it. After weeks of scavenging at garage sales and online marketplaces, you’ve pieced together a custom-built computer from a motley collection of parts. It boots, it runs, but now the real question emerges: just how powerful is this machine you’ve created? You need a way to push the CPU to its limits, a true benchmark to measure its number-crunching prowess. You don't want a generic, canned benchmark; you want something classic, elegant, and computationally demanding.

This is where an ancient mathematical marvel comes into play: the Sieve of Eratosthenes. It's more than just a method for finding prime numbers; it's a perfect algorithm to stress-test your hardware. In this guide, we'll dive deep into this algorithm, leveraging the formidable power and expressiveness of Common Lisp to build a benchmark from scratch. You'll not only find primes but also gain a profound appreciation for algorithmic efficiency and the unique capabilities of Lisp.

---

What is the Sieve of Eratosthenes?

At its core, the Sieve of Eratosthenes is an algorithm for finding prime numbers. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The numbers 2, 3, 5, 7, and 11 are prime, whereas 4, 6, 8, and 9 are not (they are called composite numbers).

The "sieve" metaphor is quite literal. Imagine you have a list of all integers starting from 2 up to a certain limit, say 30. The algorithm works by iteratively "sifting" out the composite numbers, leaving only the primes behind. It's a process of elimination rather than direct identification.

The Step-by-Step Logic

The process is remarkably straightforward and elegant:

1. Create a List: Start with a list of consecutive integers from 2 up to your target limit, n. Initially, you assume every number in this list is a potential prime.
2. Start with the First Prime: The first number in your list, 2, is a prime number. Keep it.
3. Eliminate Multiples: Go through the rest of the list and cross out all multiples of 2 (4, 6, 8, 10, and so on). These are guaranteed to be composite numbers because they are divisible by 2.
4. Move to the Next Unmarked Number: The next number in the list that hasn't been crossed out is 3. This must be a prime number. Keep it.
5. Eliminate Its Multiples: Now, go through the list and cross out all multiples of 3 (6, 9, 12, 15, etc.). Some of these, like 6, might have already been crossed out, which is fine.
6. Repeat the Process: Continue this pattern. The next unmarked number is 5 (since 4 was eliminated). Keep 5 as a prime and eliminate all of its multiples.
7. The End Condition: You only need to repeat this process for numbers up to the square root of your limit n. We'll explore why this crucial optimization works later.
8. The Result: Once you've completed this process, all the numbers that remain unmarked in your list are the prime numbers up to n.

This method avoids the costly process of trial division for every single number, making it exceptionally fast for finding all primes within a reasonable range.

Visualizing the Sieve Logic

Here is a conceptual diagram illustrating the flow of the sieving process. We start with a list of numbers and progressively eliminate multiples of discovered primes.

    ● Start (Limit n)
    │
    ▼
  ┌──────────────────────────┐
  │ Create boolean array     │
  │ `sieve` of size n+1,     │
  │ all marked `true` (prime)│
  └────────────┬─────────────┘
               │
               ▼
  ┌──────────────────────────┐
  │ For p from 2 to sqrt(n)  │
  └────────────┬─────────────┘
               │
               ▼
    ◆ Is `sieve[p]` still `true`?
   ╱             ╲
  Yes (p is prime)  No (already eliminated)
  │                 │
  ▼                 └───────────────────┐
┌──────────────────┐                    │
│ Mark all multiples │                    │
│ of p as `false`  │                    │
│ (from p*p to n)  │                    │
└─────────┬────────┘                    │
          │                             │
          └─────────────┬───────────────┘
                        ▼
  ┌───────────────────────────────────┐
  │ Loop continues to next p          │
  └───────────────────────────────────┘
                      │
                      ▼
  ┌───────────────────────────────────┐
  │ Collect all indices `i` where     │
  │ `sieve[i]` is `true`              │
  └───────────────────────────────────┘
                      │
                      ▼
                   ● End (List of primes)

---

Why Use the Sieve of Eratosthenes in Common Lisp?

While the algorithm is ancient, its implementation in a powerful language like Common Lisp reveals much about modern software development, performance, and language design. There are several compelling reasons to tackle this problem with this specific combination.

Unmatched Efficiency for Finding Primes in a Range

The primary advantage of the Sieve is its time complexity. A naive approach to finding primes, known as trial division, involves checking each number k for divisibility by all numbers from 2 up to sqrt(k). This is computationally expensive. The Sieve of Eratosthenes, on the other hand, has a time complexity of approximately O(n log log n), which is vastly superior and one of the most efficient methods for generating a complete list of primes up to a limit n.

A Perfect CPU and Memory Benchmark

The algorithm is an excellent candidate for benchmarking because it heavily utilizes both integer arithmetic and memory access. It requires allocating a potentially large block of memory (the sieve array) and then performing a series of systematic read and write operations across it. This tests a system's memory bandwidth, cache performance, and the CPU's ability to handle tight loops with simple arithmetic—core components of overall system performance.

Showcasing the Power of Common Lisp

Common Lisp is not just another programming language; it's an interactive, dynamic, and highly performant system. Implementing the Sieve showcases several of its key strengths:

• The loop Macro: As you'll see in the code, Common Lisp's loop macro is a mini-language in itself, allowing for highly expressive and complex iteration patterns to be written in a clear, declarative style.
• Performance: Modern Common Lisp compilers like SBCL (Steel Bank Common Lisp) produce highly optimized machine code that can rival or even exceed the performance of languages like C or C++.
• Data Structures: The language provides efficient, low-level data structures like arrays and bit-vectors, which are perfect for implementing the sieve.

By tackling this problem, you are not just solving a puzzle from the kodikra learning path; you are learning to wield a powerful tool for high-performance computing.

---

How to Implement the Sieve in Common Lisp: A Code Deep Dive

Now, let's dissect the elegant Common Lisp solution provided in the kodikra.com curriculum. We will go through it section by section to understand the logic, syntax, and the idiomatic Lisp way of thinking.

The Complete Code

Here is the full implementation for context. We will break it down immediately after.

(defpackage :sieve
  (:use :cl)
  (:export :primes-to)
  (:documentation "Generates a list of primes up to a given limit."))

(in-package :sieve)

(defun primes-to (n)
  "List primes up to `n' using sieve of Eratosthenes."
  (loop
    initially
       (when (< n 2) (return nil))
    with sqrtn = (1+ (isqrt n))
    with sieve = (make-array (1+ n) :element-type 'boolean :initial-element t)
    
    for maybe from 2 to sqrtn
    when (aref sieve maybe)
      do (loop for multiple from (* maybe maybe) to n by maybe
               do (setf (aref sieve multiple) nil))

    finally
       (return (loop for i from 2 to n
                     when (aref sieve i)
                       collect i))))

Part 1: Setting Up the Package

(defpackage :sieve
  (:use :cl)
  (:export :primes-to)
  (:documentation "Generates a list of primes up to a given limit."))

(in-package :sieve)

• (defpackage :sieve ...): This defines a new package named sieve. In Common Lisp, packages are namespaces that prevent symbol collisions. It's like a module or library in other languages.
• (:use :cl): This clause specifies that our new package should inherit all the standard symbols from the :cl (Common Lisp) package, so we can use functions like defun, loop, and make-array without a prefix.
• (:export :primes-to): This is crucial. It declares that the symbol primes-to should be public. Any other code that uses this package will be able to access our main function.
• (in-package :sieve): This command switches the current working namespace to our newly created sieve package. All subsequent definitions will belong to it.

Part 2: The `primes-to` Function and the Mighty `loop` Macro

The core of the logic resides within the primes-to function, which is almost entirely built around a single, powerful loop expression.

(defun primes-to (n)
  "List primes up to `n' using sieve of Eratosthenes."
  (loop ... ))

The loop macro is a standout feature of Common Lisp. It provides a structured, English-like syntax for expressing complex iterations. Let's break down its clauses.

The Initialization Block (`initially` and `with`)

    initially
       (when (< n 2) (return nil))
    with sqrtn = (1+ (isqrt n))
    with sieve = (make-array (1+ n) :element-type 'boolean :initial-element t)

• initially: This clause contains code that runs exactly once, before any iteration begins.
  • (when (< n 2) (return nil)): This is a guard clause. Prime numbers start at 2, so if the input limit n is less than 2, we immediately return an empty list nil.
• with: This clause is used to declare and initialize variables that are local to the loop.
  • sqrtn = (1+ (isqrt n)): This calculates the integer square root of n and adds 1. We only need to find primes up to this limit to mark all composites, a key optimization. isqrt is the integer square root function.
  • sieve = (make-array (1+ n) ...): This is the heart of the sieve. It creates a one-dimensional array of size n + 1.
    • :element-type 'boolean: This specifies that the array will hold boolean values (t for true and nil for false). In Common Lisp, t and nil are the canonical boolean values.
    • :initial-element t: Every element in the array is initialized to t. This represents our initial assumption that every number from 0 to n is a prime.

The Main Sieving Loop (`for`, `when`, `do`)

    for maybe from 2 to sqrtn
    when (aref sieve maybe)
      do (loop for multiple from (* maybe maybe) to n by maybe
               do (setf (aref sieve multiple) nil))

• for maybe from 2 to sqrtn: This is the main iteration clause. It loops the variable maybe from 2 up to the calculated square root of n. maybe represents a potential prime number whose multiples we need to eliminate.
• when (aref sieve maybe): This is a conditional clause. It executes the following do block only if the condition is true. (aref sieve maybe) retrieves the value at the index maybe in our sieve array. If it's t, it means maybe is a prime number (it hasn't been marked as a multiple of a smaller prime).
• do (loop ...): If maybe is a prime, we execute this inner loop to mark all its multiples.
  • for multiple from (* maybe maybe) to n by maybe: This inner loop is efficient. It starts marking from maybe * maybe, not 2 * maybe, because smaller multiples (like 2 * maybe, 3 * maybe) would have already been marked by smaller primes (2, 3, etc.). It iterates up to n, incrementing by maybe each time.
  • do (setf (aref sieve multiple) nil): This is the "sieving" action. It sets the value at the index multiple to nil (false), marking it as a composite number.

The Final Collection Block (`finally`)

    finally
       (return (loop for i from 2 to n
                     when (aref sieve i)
                       collect i))

• finally: This clause contains code that runs exactly once, after all iterations are complete.
• (return (loop ...)): It returns the result of another, final loop expression.
  • for i from 2 to n: This loop iterates through our entire sieve array, from index 2 to n.
  • when (aref sieve i): It checks if the number i is still marked as prime (i.e., the value at sieve[i] is t).
  • collect i: If the condition is true, the collect keyword gathers the value of i into a list. This list is automatically built by the loop macro and is the final value returned by the function.

Visualizing the Common Lisp `loop` Flow

The `loop` macro in this solution has a distinct, multi-stage execution flow which can be visualized as follows.

    ● Start `(primes-to n)`
    │
    ▼
  ┌──────────────────────────┐
  │ `initially` block        │
  │  - Check if n < 2        │
  └────────────┬─────────────┘
               │
               ▼
  ┌──────────────────────────┐
  │ `with` block             │
  │  - Calculate `sqrtn`     │
  │  - Allocate `sieve` array│
  └────────────┬─────────────┘
               │
               ▼
  ┌──────────────────────────┐
  │ Main `for` loop begins   │
  │ (from 2 to `sqrtn`)      │
  └────────────┬─────────────┘
               │
    ◆ `when (aref sieve maybe)`?
   ╱             ╲
  Yes              No
  │                │
  ▼                └───────────┐
┌─────────────────┐            │
│ Inner `do` loop │            │
│ marks multiples │            │
│ as `nil`        │            │
└────────┬────────┘            │
         │                     │
         └──────────┬──────────┘
                    ▼
  ┌───────────────────────────────────┐
  │ Main `for` loop continues         │
  └───────────────────────────────────┘
                    │
                    ▼
  ┌───────────────────────────────────┐
  │ `finally` block executes          │
  │  - A new `loop` collects results  │
  └───────────────────────────────────┘
                    │
                    ▼
                 ● Return (List of primes)

---

Performance Considerations and Optimizations

The provided solution is already quite performant and idiomatic. However, in the world of high-performance computing, there are always trade-offs to consider. For a deeper understanding, let's look at the pros, cons, and a potential optimization.

Pros and Cons of This Approach

Pros	Cons
Highly Efficient Time Complexity: At O(n log log n), it's one of the fastest ways to find all primes in a given range.	High Space Complexity: The algorithm requires O(n) memory to store the sieve array. For very large n (e.g., in the billions), this can become prohibitive.
Readability and Expressiveness: The Common Lisp loop macro makes the complex logic declarative and relatively easy to follow compared to nested C-style for-loops.	Not Ideal for Single Primes: If you only need to check if one very large number is prime, trial division or probabilistic tests like Miller-Rabin are far more memory-efficient.
Simple Core Logic: The underlying principle of eliminating multiples is easy to understand and reason about.	Fixed Upper Bound: The sieve is generated for a fixed limit n. It cannot be easily extended to find primes beyond that limit without re-running the entire process.

Optimization: Using a Bit Vector for Memory Efficiency

For very large values of n, the memory usage of a boolean array can be a bottleneck. Each boolean might take a full byte (8 bits) of memory. Common Lisp provides a more space-efficient data structure for this exact scenario: the bit-vector.

A bit vector is an array where each element is just a single bit (0 or 1). This can reduce memory usage by a factor of 8 or more.

Here’s how you could modify the solution to use a bit vector:

(defun primes-to-optimized (n)
  "List primes up to `n' using a memory-optimized bit-vector sieve."
  (loop
    initially
       (when (< n 2) (return nil))
    with sqrtn = (1+ (isqrt n))
    ;; The key change is here: :element-type 'bit and :initial-element 1
    with sieve = (make-array (1+ n) :element-type 'bit :initial-element 1)
    
    for maybe from 2 to sqrtn
    ;; We check for 1 instead of t
    when (= 1 (aref sieve maybe))
      do (loop for multiple from (* maybe maybe) to n by maybe
               ;; We set to 0 instead of nil
               do (setf (aref sieve multiple) 0))

    finally
       (return (loop for i from 2 to n
                     ;; Check for 1 again
                     when (= 1 (aref sieve i))
                       collect i))))

In this version, we use 1 to represent "is prime" and 0 for "is composite". The logic is identical, but the underlying sieve array is far more compact in memory. This is a classic space-time tradeoff; while it saves memory, bit-level access might be marginally slower on some architectures than byte-level access, but for large n, the memory savings are almost always worth it.

---

Frequently Asked Questions (FAQ)

What is the time complexity of the Sieve of Eratosthenes?

The time complexity is approximately O(n log log n). This is because the main work is done in the inner loops that mark multiples. The number of marking operations is proportional to n/2 + n/3 + n/5 + ..., which converges to n log log n. This makes it significantly faster than trial division for finding all primes up to n.

Why do we only need to iterate up to the square root of the limit `n`?

This is a critical optimization. Any composite number c can be factored into a * b. If both a and b were greater than sqrt(n), then their product a * b would be greater than n. Therefore, at least one factor of any composite number less than or equal to n must be less than or equal to sqrt(n). By the time our outer loop reaches sqrt(n), we have already found the smallest prime factor for every composite number up to n and marked them.

Can the Sieve of Eratosthenes be used for very large numbers?

The standard Sieve is limited by memory. Since it requires an array of size n, finding primes up to, say, 10¹² would require terabytes of RAM, which is impractical. For such large numbers, more advanced techniques like a segmented sieve (which sieves in blocks) or probabilistic primality tests (like Miller-Rabin) are used.

How does this Common Lisp implementation handle memory?

The implementation allocates a single, contiguous array (or bit-vector) of size n+1 on the heap. Common Lisp has a sophisticated automatic memory management system (a garbage collector), so once the primes-to function returns its list of primes, the large sieve array is no longer referenced and will be automatically deallocated by the system, freeing up the memory.

What's the difference between the Sieve of Eratosthenes and trial division?

Trial division is a primality test for a single number. To find if k is prime, you try dividing it by all primes up to sqrt(k). The Sieve of Eratosthenes is a prime number generator. It finds all primes up to a limit n in one pass. Using trial division to generate a list of primes is much slower because you re-do work for each number independently.

Is the `loop` macro the only way to implement this in Common Lisp?

No, but it is often the most expressive and efficient for this kind of array-based iteration. You could also implement it using other constructs like dotimes, do, or even recursive functional approaches. However, the loop macro is specifically designed for these complex, multi-stage iterations and often allows the compiler to generate the most optimized machine code.

What are some real-world applications of finding prime numbers?

Prime numbers are the foundation of modern public-key cryptography, such as the RSA algorithm, which secures most of the internet's communication (HTTPS, SSH, etc.). They are also used in generating hash functions, in pseudo-random number generators, and are a fundamental area of research in number theory and mathematics.

---

Conclusion: An Ancient Algorithm in a Modern Context

The Sieve of Eratosthenes is a beautiful testament to the timelessness of a great algorithm. Its simple concept of elimination belies a powerful efficiency that has kept it relevant for over two millennia. By implementing it in Common Lisp, we not only create a practical tool for finding prime numbers but also a formidable benchmark for testing a computer's core performance.

Through this exploration, we've seen how Common Lisp's features, particularly the expressive loop macro and efficient array handling, make it an outstanding choice for performance-critical tasks. You've learned how to structure a Lisp program with packages, how to write complex, multi-stage loops declaratively, and how to reason about crucial optimizations like the square root limit and the use of bit-vectors.

This exercise, drawn from the exclusive kodikra.com Common Lisp curriculum, is more than just a coding challenge. It's an invitation to think like a computer scientist—balancing time against space, readability against raw performance, and appreciating the deep connection between mathematics and software.

Disclaimer: The code and explanations in this article are based on modern Common Lisp standards, exemplified by implementations like SBCL 2.4+. The core concepts are stable, but always consult the documentation for your specific Lisp implementation for any minor variations.

---

Published by Kodikra — Your trusted Common-lisp learning resource.