Sieve in Coffeescript: Complete Solution & Deep Dive Guide

---

The Complete Guide to Sieve of Eratosthenes in CoffeeScript: From Zero to Prime Number Hero

The Sieve of Eratosthenes is an ancient and highly efficient algorithm for finding all prime numbers up to a specified integer. This guide explains how to implement it in CoffeeScript, using list filtering and boolean arrays to progressively eliminate multiples of primes, resulting in a clean list of primes within a given limit.

You've just scored a massive box of random computer parts at a garage sale. The thrill of the build is upon you, and you start piecing together custom machines. But how do you know if your creations are any good? You need a way to benchmark their performance, to push their CPUs to the limit and see how they stack up. You decide on a classic, elegant, yet surprisingly demanding test: implementing the Sieve of Eratosthenes.

You might be thinking, "An ancient algorithm? How can that test modern hardware?" The beauty of the Sieve lies in its deceptive simplicity and its demand for efficient memory and processing. It's the perfect challenge. This guide will not only demystify the algorithm's logic but also walk you through a complete, line-by-line implementation in CoffeeScript, transforming a complex mathematical concept into clean, readable, and powerful code. Let's start building our benchmark.

---

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an algorithm attributed to the ancient Greek mathematician Eratosthenes of Cyrene. It's a remarkably efficient method for finding all prime numbers up to a specified integer. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself (e.g., 2, 3, 5, 7, 11).

The core idea is brilliantly simple: instead of testing each number for primality one by one, we work with a list of all numbers and systematically eliminate, or "sieve out," the numbers that are not prime (i.e., composite numbers). A composite number is a natural number that can be formed by multiplying two smaller natural numbers.

Imagine you have a grid of numbers. You start with the first prime, 2, and cross out all of its multiples (4, 6, 8, ...). Then you move to the next number that isn't crossed out, which is 3, and cross out all of its multiples (6, 9, 12, ...). You repeat this process, and the numbers that remain standing at the end are the primes. This method avoids redundant checks and is significantly faster than brute-force approaches for finding primes within a reasonable range.

---

Why Use the Sieve Algorithm?

In the world of computer science, efficiency is king. While you could write a simple loop to check every number up to a limit for primality, this approach, known as trial division, is incredibly slow. Its time complexity is roughly O(n * sqrt(n)), which becomes unmanageable for large limits.

The Sieve of Eratosthenes, by contrast, boasts a time complexity of O(n log log n). This makes it one of the most efficient algorithms for this specific task. Its elegance and performance are why it's a staple in programming education, competitive programming, and even practical applications.

Key Advantages:

• Speed: It's significantly faster than trial division for finding all primes up to a limit n.
• Simplicity: The underlying concept is straightforward to understand and implement.
• Educational Value: It's a fantastic exercise for learning about algorithms, array manipulation, and performance optimization, as you'll see in this kodikra module.
• Practical Applications: Prime numbers are the bedrock of modern cryptography (like RSA encryption). While other algorithms are used for finding the massive primes needed for security, the Sieve is fundamental to number theory and is often a building block in more complex algorithms.

---

How Does the Sieve of Eratosthenes Work?

Let's break down the algorithm into a step-by-step process. The "sieve" is a metaphor for a tool with holes that lets some things (primes) pass through while catching others (composites). We'll simulate this with a list or an array.

The Logical Steps

1. Create a List: Start by generating a list of consecutive integers from 2 up to your desired limit, let's call it n.
2. Initialize the First Prime: The first number in our list, 2, is the first prime. Let's call our current prime p. So, we start with p = 2.
3. Mark the Multiples: Go through your list and eliminate (or "mark") all multiples of p. For p = 2, you would mark 4, 6, 8, 10, and so on, up to n. You don't mark p itself.
4. Find the Next Prime: Move to the next number in your list that has not been marked. This number is the next prime. Update p to this new prime. In our case, after handling 2, the next unmarked number is 3.
5. Repeat the Process: Repeat step 3 with the new p. With p = 3, you would mark 6, 9, 12, 15, etc. Notice that some numbers, like 6, will be marked more than once, which is fine.
6. The Stopping Condition: You only need to continue this process until p * p > n. Why? Because if a number k is composite, it must have a prime factor less than or equal to sqrt(k). Therefore, any composite number less than n will have already been marked by a prime less than or equal to sqrt(n). This is a key optimization.
7. Collect the Results: Once the process is complete, all the numbers that remain unmarked in your list are the prime numbers up to n.

Visualizing the Flow

Here is a simplified flow diagram of the algorithm's logic:

    ● Start (limit n)
    │
    ▼
  ┌─────────────────────────┐
  │ Create list [2, 3, ..., n] │
  └────────────┬────────────┘
               │
               ▼
    Let p = 2 (first prime)
    │
    ├─► Loop while p*p ≤ n ──────────┐
    │    │                           │
    │    ▼                           │
    │  ┌──────────────────────────┐  │
    │  │ Mark all multiples of p  │  │
    │  │ (2p, 3p, ...) as composite │  │
    │  └────────────┬─────────────┘  │
    │               │                │
    │               ▼                │
    │  Find next unmarked number     │
    │  and set it as the new p       │
    │    │                           │
    └────┴───────────────────────────┘
         │
         ▼
  ┌─────────────────────────┐
  │ Collect all unmarked numbers │
  └────────────┬────────────┘
               │
               ▼
            ● End

---

Where is this Implemented? The CoffeeScript Code Walkthrough

CoffeeScript's expressive and minimal syntax makes it a joy to write algorithms like the Sieve. The solution provided in the kodikra CoffeeScript learning path uses a clever, functional approach with array filtering. Let's analyze it in detail.

The Initial Solution Code

class Sieve
  @primes: (limit) ->
    results = []

    if limit < 2
      return []

    numbers = [2..limit]

    while numbers.length > 0
      [curr, numbers...] = numbers
      results.push curr
      numbers = numbers.filter (n) -> n % curr != 0

    results

module.exports = Sieve

Line-by-Line Code Breakdown

This implementation is concise and highly readable, leveraging some of CoffeeScript's best features.

class Sieve

This defines a class named Sieve. In this case, it's used more as a namespace to hold our static method rather than for creating instances.

@primes: (limit) ->

The @ symbol in CoffeeScript defines a static property on the class itself, equivalent to Sieve.primes in JavaScript. We are defining a static method called primes that accepts one argument, limit.

results = []

We initialize an empty array called results. This array will store the prime numbers we find throughout the process.

if limit < 2 ... return []

This is a crucial edge case handler. By definition, there are no prime numbers less than 2. If the user provides a limit of 1, 0, or a negative number, we immediately return an empty array to avoid unnecessary computation.

numbers = [2..limit]

This is CoffeeScript's elegant range syntax. It creates an array of integers starting from 2 and going up to and including limit. For a limit of 10, this creates the array [2, 3, 4, 5, 6, 7, 8, 9, 10].

while numbers.length > 0

This loop forms the core of our algorithm. It will continue to execute as long as there are any numbers left in our `numbers` array to process.

[curr, numbers...] = numbers

This is a powerful piece of CoffeeScript syntax: destructuring assignment with a splat.

• curr gets assigned the first element of the numbers array.
• numbers... (the splat operator) collects the rest of the elements into a new array, which is then reassigned back to the numbers variable.

For the first iteration, curr becomes 2, and numbers becomes [3, 4, 5, 6, 7, 8, 9, 10]. This effectively "pulls off" the first number, which we know is a prime.

results.push curr

Since we just pulled the next known prime off the front of the list, we add it to our results array. In the first iteration, we add 2 to results.

numbers = numbers.filter (n) -> n % curr != 0

This is the "sieving" step. We use the filter array method to create a new `numbers` array. The filter keeps only the elements n for which the condition n % curr != 0 is true. In other words, it removes all numbers that are perfectly divisible by our current prime, curr.

• In the first iteration, curr is 2. The filter removes 4, 6, 8, and 10. The numbers array becomes [3, 5, 7, 9].
• In the next iteration, curr becomes 3, and numbers becomes [5, 7, 9]. The filter removes 9. The numbers array becomes [5, 7].

This process continues until the `numbers` array is empty.

results

In CoffeeScript, the last expression in a function is implicitly returned. So, once the while loop finishes, the final results array is returned.

---

When to Optimize? A More Performant Approach

The functional, filter-based solution is elegant and easy to understand. However, it has a significant performance drawback for large limits. In each iteration of the while loop, the line numbers = numbers.filter(...) creates an entirely new array in memory. For a large limit, this leads to a massive number of memory allocations and garbage collection cycles, which can slow the program down considerably.

A more traditional and performant implementation uses a boolean array (or a similar data structure) to "mark" composite numbers instead of removing them. This avoids creating new arrays in a loop.

The Optimized Solution using a Boolean Sieve

class Sieve
  @primes: (limit) ->
    if limit < 2
      return []

    # Create a boolean array, `isPrime`, initialized to true
    # Indices will correspond to numbers (e.g., isPrime[5] is for number 5)
    isPrime = (true for i in [0..limit])

    # 0 and 1 are not prime numbers
    isPrime[0] = isPrime[1] = false

    # Iterate from 2 up to the square root of the limit
    for p in [2..Math.sqrt(limit)]
      # If p is still marked as prime...
      if isPrime[p]
        # ...then mark all of its multiples as not prime.
        # We can start marking from p*p. Why? Multiples less than p*p
        # (like 2*p, 3*p) would have already been marked by smaller primes.
        for multiple in [p*p..limit] by p
          isPrime[multiple] = false

    # Collect the results by finding the indices that are still true
    primes = []
    for num in [2..limit]
      if isPrime[num]
        primes.push num

    primes

module.exports = Sieve

Analysis of the Optimization

• Memory Efficiency: We create only one primary data structure, the isPrime boolean array. We modify it in place instead of creating new arrays repeatedly. This drastically reduces memory churn.
• CPU Efficiency: Iterating and changing boolean flags is computationally cheaper than filtering and allocating new arrays.
• Key Optimizations:
  • The outer loop only goes up to Math.sqrt(limit), which is a massive performance gain.
  • The inner loop for marking multiples starts at p*p, avoiding redundant work.

Visualizing the Optimized Flow (Boolean Array)

This diagram shows the logic of marking indices in a boolean array.

    ● Start (limit n)
    │
    ▼
  ┌───────────────────────────────────┐
  │ Create boolean array `isPrime`    │
  │ of size n+1, all set to `true`    │
  └─────────────────┬─────────────────┘
                    │
                    ▼
  Mark `isPrime[0]` and `isPrime[1]` as `false`
  │
  ├─► Loop p from 2 to sqrt(n) ────────┐
  │    │                               │
  │    ▼                               │
  │  ◆ if isPrime[p] is true?          │
  │  ╱                ╲                │
  │ Yes                No              │
  │  │                  │              │
  │  ▼                  └─(continue)─┐ │
  │ ┌──────────────────────────────┐ │ │
  │ │ Mark all multiples of p      │ │ │
  │ │ from p*p to n as `false`     │ │ │
  │ └──────────────────────────────┘ │ │
  │    │                             │ │
  └────┴─────────────────────────────┘ │
       └───────────────────────────────┘
                    │
                    ▼
  ┌───────────────────────────────────┐
  │ Collect all numbers `i` where     │
  │ `isPrime[i]` is `true`             │
  └─────────────────┬─────────────────┘
                    │
                    ▼
                 ● End

---

Pros & Cons: Comparing the Two Approaches

To provide a clear picture, let's compare the two CoffeeScript implementations discussed in this guide. Both are valid, but they serve different purposes—one prioritizing readability and the other prioritizing raw performance.

Feature	Functional (Filter-Based) Approach	Optimized (Boolean Array) Approach
Readability	Excellent. The logic flows naturally and reads like a description of the process. Very idiomatic CoffeeScript.	Good, but requires understanding array indices and the sqrt(n) optimization. More classical algorithm style.
Performance	Poor for large limits due to high memory allocation and garbage collection overhead from creating new arrays in each loop.	Excellent. Very low memory overhead and computationally fast. This is the standard high-performance implementation.
Memory Usage	High. Continuously creates new, smaller arrays, leading to significant memory churn.	Low and predictable. A single boolean array of size limit + 1 is allocated once.
Best For	Small limits, educational purposes, or situations where code clarity is paramount over speed.	Large limits, performance-critical applications, benchmarking, and competitive programming.

---

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 sum of the reciprocals of primes approaches log log n, making this algorithm highly efficient.

Why does the algorithm only need to check primes up to the square root of the limit?

Any composite number c can be factored into a * b. If both a and b were greater than sqrt(c), then their product a * b would be greater than c, which is a contradiction. Therefore, at least one prime factor of any composite number must be less than or equal to its square root. By the time we've sieved out the multiples of all primes up to sqrt(limit), we have effectively removed all composite numbers up to limit.

Can the Sieve be used for very large numbers?

The primary limitation is memory. The standard Sieve requires an array of size proportional to the limit n. If you need to find primes up to 1 billion, you'd need a boolean array with 1 billion elements, requiring about 1 GB of RAM. For even larger numbers, more advanced, memory-efficient variations like the "Segmented Sieve" are used.

How does CoffeeScript's syntax simplify this algorithm?

CoffeeScript's features like ranges ([2..limit]), destructuring with splats ([curr, numbers...] = numbers), and implicit returns make the code significantly more concise and readable compared to its JavaScript equivalent, especially in the functional-style implementation.

Is the Sieve of Eratosthenes the only way to find prime numbers?

No, there are many other algorithms. For finding all primes in a range, the Sieve of Atkin is even faster (O(n / log log n)) but is much more complex to implement. For testing if a single, very large number is prime, probabilistic tests like the Miller-Rabin primality test are used.

What are some practical applications of finding prime numbers?

The most well-known application is in public-key cryptography, such as the RSA algorithm, which relies on the difficulty of factoring the product of two very large prime numbers. They are also fundamental in number theory, hashing algorithms, and generating pseudo-random numbers.

---

Conclusion: Sieving Your Way to Mastery

You've successfully journeyed from a box of computer parts to implementing one of history's most elegant algorithms. The Sieve of Eratosthenes is more than just a method for finding prime numbers; it's a lesson in computational thinking. We explored a beautifully expressive, functional approach in CoffeeScript and then refactored it into a highly performant, memory-efficient version suitable for serious benchmarking.

This exercise from the kodikra.com exclusive curriculum demonstrates the trade-offs between readability and performance—a core concept in software engineering. By understanding both implementations, you are better equipped to choose the right tool for the job. You now have a powerful benchmarking program and a deeper appreciation for algorithmic efficiency.

Ready for the next challenge? Continue your journey on the kodikra CoffeeScript learning path to tackle more complex problems, or explore our complete CoffeeScript guide to master the language's powerful features.

Disclaimer: All code snippets are based on the latest stable language versions at the time of writing. CoffeeScript syntax is stable, but the underlying JavaScript engine and its performance characteristics continue to evolve.

---

Published by Kodikra — Your trusted Coffeescript learning resource.