Home
8
8th

Sieve in 8th: Complete Solution & Deep Dive Guide

Tabs labeled

Sieve of Eratosthenes in 8th: A Zero-to-Hero Guide to Finding Prime Numbers

The Sieve of Eratosthenes is an ancient, highly efficient algorithm for finding all prime numbers up to a specified integer. This guide explains its logic, historical significance, and provides a complete implementation in the 8th programming language, detailing how to filter out composite numbers to isolate primes.

The Garage Sale Benchmark: A Programmer's Tale

Imagine this: you stumble upon a garage sale and find a treasure trove—a big box filled with random, assorted computer parts. You see potential. You start mixing and matching CPUs, RAM sticks, and motherboards, piecing together custom-built machines. But a critical question arises: how do you measure their performance? How do you know which combination is a powerhouse and which is just a pretty box?

You decide against off-the-shelf benchmarking software. You want something pure, something that tests raw computational power. You need a challenge that will push these custom rigs to their limits. The answer lies not in modern graphics rendering, but in ancient mathematics: the famous "Sieve of Eratosthenes." It's an algorithm that is elegant, simple to understand, yet computationally intensive enough to be a perfect stress test. This guide will not only help you build that benchmark but will also give you a deep understanding of one of the most foundational algorithms in computer science, implemented in the powerful 8th language.

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to a given limit, n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Think of numbers like 2, 3, 5, 7, 11, and so on. Numbers like 4 (divisible by 2), 6 (divisible by 2 and 3), and 9 (divisible by 3) are called composite numbers.

The name "sieve" is a perfect metaphor for how the algorithm works. Imagine you have a container full of sand and pebbles, and you want to separate them. You would use a sieve—a mesh screen that lets the fine sand fall through while catching the larger pebbles. Eratosthenes' algorithm does the same for numbers. It starts with a list of all integers up to a certain limit and systematically "sifts out" the composite numbers, leaving only the primes behind.

The core idea is brilliantly simple: an integer is prime if it is not a multiple of any smaller prime. Instead of testing each number for divisibility (a slow process), the sieve proactively eliminates all multiples of primes it discovers.

Why Use This Ancient Algorithm Today?

Developed by the Greek mathematician Eratosthenes of Cyrene in the 3rd century BC, this algorithm has stood the test of time for several compelling reasons. Its elegance and efficiency are remarkable, even by modern standards.

Unmatched Efficiency for a Range of Primes

When you need to find all primes up to a certain number n, the Sieve of Eratosthenes is dramatically faster than testing each number individually. The most basic method, known as trial division, involves checking every number up to n to see if it's divisible by any number smaller than itself. This is incredibly slow.

The Sieve, on the other hand, has a time complexity of approximately O(n log log n). For non-computer scientists, this means the time it takes to run grows very slowly as the input number n gets larger. This makes it one of the most efficient algorithms for generating a list of primes within a practical range.

A Foundation for More Complex Problems

Understanding the Sieve is a rite of passage for programmers. It teaches fundamental concepts like array manipulation, boolean logic, and algorithmic optimization. The principles learned from implementing it are directly applicable to a wide range of problems in number theory, competitive programming, and project Euler-style challenges.

Modern Applications in Cryptography and Research

While modern cryptography often requires finding single, massive prime numbers (for which other algorithms like Miller-Rabin are used), the Sieve remains crucial. It's often used as a preliminary step to generate a base list of smaller primes, which can then be used to speed up more complex primality tests for larger numbers. It's also a foundational tool in mathematical research and computational number theory.

How the Sieve of Eratosthenes Works: A Step-by-Step Breakdown

Let's break down the logic of the algorithm. We'll find all prime numbers up to a limit, say n = 30.

  1. Create a List: First, we create a list of consecutive integers from 2 up to our limit n. We'll also maintain a boolean list (or array), let's call it is_prime, of the same size. Initially, we assume every number in this range is a prime, so we set all entries in is_prime to true.
  2. Start with the First Prime: We start with the first prime number, which we know is p = 2.
  3. Mark the Multiples: We then go through our list and "cross out" or mark all multiples of p as not prime (i.e., set their corresponding entry in is_prime to false). For p = 2, we would mark 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, and 30 as not prime.
  4. Move to the Next Unmarked Number: We then find the next number in our list that has not been marked. In our case, this is 3. This number must be a prime because it wasn't a multiple of any smaller prime (only 2 in this case).
  5. Repeat the Process: We set our new prime to p = 3 and repeat the process of marking its multiples: 6, 9, 12, 15, 18, 21, 24, 27, 30. Notice that some of these (like 6 and 12) were already marked, which is fine.
  6. Continue Until You Reach the Limit: We continue this process. The next unmarked number is 5. We mark its multiples: 10, 15, 20, 25, 30. The next is 7. We mark its multiples: 14, 21, 28.
  7. The Final Result: Once we've gone through this process, all the numbers that remain "unmarked" in our is_prime list are the prime numbers up to n.

This entire logical flow can be visualized as a filtering process, which is where the "sieve" analogy comes from.

    ● Start (Limit n)
    │
    ▼
  ┌─────────────────────────────┐
  │ Create boolean array `A`    │
  │ of size n+1, all `true`     │
  └─────────────┬───────────────┘
                │
    ┌───────────┴───────────┐
    │ Set A[0], A[1] = `false`│
    └───────────┬───────────┘
                │
                ▼
  Initialize loop: p = 2 to sqrt(n)
                │
    ┌───────────┴───────────┐
    │ Loop (p)              │
    └───────────┬───────────┘
                │
                ▼
        ◆ Is A[p] true?
       ╱               ╲
      Yes               No
      │                 │
      ▼                 ▼
┌──────────────────┐   (Continue to next p)
│ Mark multiples   │
│ Loop j from p*p  │
│ to n, step p     │
│ Set A[j] = `false` │
└──────────────────┘
      │
      └─────────────────┤
                        │
                        ▼
    ● End Loop (p)
    │
    ▼
  ┌─────────────────────────────┐
  │ Collect all indices `i`     │
  │ where A[i] is `true`        │
  └─────────────┬───────────────┘
                │
                ▼
    ● Finish (List of Primes)

The 8th Implementation: Code and Walkthrough

Now, let's translate this logic into the 8th programming language. 8th is a stack-based language, which means we operate on data by pushing it onto and popping it off a stack. Functions, called "words" in 8th, consume their inputs from the stack and leave their results on the stack.

Our implementation will be structured into a few helper words and one main word, sieve, which takes the limit n and returns an array of primes.


\ Sieve of Eratosthenes implementation from kodikra.com's exclusive curriculum

\ Word to initialize the boolean array (called a 'sieve' here)
\ n -- a
: sieve:init \ limit -> sieve-array
  1+              \ Add 1 to limit to get array size (0 to n)
  [ 1, swap repeat ] a:new  \ Create a new array of size n+1 filled with 1s (true)
  dup 0 0 a:set   \ Set index 0 to 0 (false)
  dup 1 0 a:set   \ Set index 1 to 0 (false)
;

\ Word to perform the main sieving process
\ a -- a
: sieve:run \ sieve-array -> sieve-array
  dup a:len 1- sqrt -> n_sqrt \ Get the square root of the limit
  2 -> i \ Initialize our prime candidate 'i' to 2
  (
    dup i a:get          \ Get the boolean value at index i
    (
      i i * -> j         \ Start marking from i*i
      (
        dup j 0 a:set    \ Set the multiple at index j to 0 (false)
        i + -> j         \ Move to the next multiple
        j over a:len <   \ Check if j is still within bounds
      ) while
      drop \ Clean up the array from the inner loop
    ) if

    i 1+ -> i            \ Increment i to the next number
    i n_sqrt <=          \ Loop condition: continue while i <= sqrt(n)
  ) while
;

\ Word to collect the prime numbers from the sieved array
\ a -- a
: sieve:collect \ sieve-array -> primes-array
  [] a:new -> primes \ Create a new empty array for the results
  dup a:len -> len   \ Get the length of the sieve array
  0 -> i             \ Initialize index 'i' to 0
  (
    dup i a:get      \ Get the boolean value at index i
    ( i primes a:push ) if \ If true (1), push the index to our primes array

    i 1+ -> i        \ Increment i
    i len <          \ Loop condition: continue while i < len
  ) while
  drop               \ Drop the sieve array
  primes             \ Leave the primes array on the stack
;

\ Main word that combines all steps
\ n -- a
: sieve \ limit -> primes-array
  sieve:init
  sieve:run
  sieve:collect
;

\ Example Usage:
\ 30 sieve .
\ Output: [2,3,5,7,11,13,17,19,23,29]

Detailed Code Walkthrough

Let's dissect this 8th code block by block to understand how it manipulates the stack to achieve our goal.

1. sieve:init

This word is responsible for creating our boolean array, which we'll call our sieve plate.

  • \ limit -> sieve-array: This is a stack comment. It tells us the word expects a limit (n) on the stack and will leave an array on the stack.
  • 1+: Takes the limit n from the stack, adds 1, and pushes the result (n+1). We need this because we want to include n itself, and arrays are often 0-indexed.
  • [ 1, swap repeat ] a:new: This is idiomatic 8th for creating a pre-filled array. swap puts n+1 before the 1. repeat creates a list of n+1 ones. a:new converts this list into an array. The stack now holds our array, where every element is 1 (representing true).
  • dup 0 0 a:set: dup duplicates the array reference. 0 0 a:set takes the array, an index (0), and a value (0), and sets the element at that index. We mark 0 as not prime.
  • dup 1 0 a:set: Similarly, we mark 1 as not prime. The final, initialized array is left on the stack.

2. sieve:run

This is the heart of the algorithm where the "sieving" happens.

  • dup a:len 1- sqrt -> n_sqrt: We duplicate the array reference, get its length, subtract 1 to get our original limit n, calculate its square root, and store it in a temporary variable n_sqrt. This is a key optimization.
  • 2 -> i: We initialize our loop counter i (our prime candidate) to 2.
  • ( ... ) while: This is the main outer loop, which continues as long as i is less than or equal to the square root of n.
  • dup i a:get: Inside the loop, we duplicate the array and get the value at index i. This value (0 or 1) is pushed to the stack.
  • ( ... ) if: This checks the value we just got. If it's 1 (true), it means i is a prime, and we execute the inner block to mark its multiples.
  • i i * -> j: Inside the if block, we calculate i*i and store it in j. This is our second key optimization; we start marking from the square of the prime.
  • ( ... ) while: This is the inner loop for marking multiples.
  • dup j 0 a:set: Marks the multiple at index j as not prime (sets it to 0).
  • i + -> j: Increments j by i to get the next multiple (e.g., from i*i to i*i + i).
  • j over a:len <: The loop condition. over copies the array reference from deeper in the stack to the top. We check if j is still inside the array bounds.
  • drop: After the inner loop finishes, it leaves the array reference on the stack, which we drop to clean up.
  • i 1+ -> i: We increment i for the outer loop.

3. sieve:collect

This final helper word iterates through the marked-up sieve array and gathers all the indices that are still marked as prime.

  • [] a:new -> primes: Creates a new, empty array called primes to store our results.
  • dup a:len -> len: Gets the length of the sieve array and stores it.
  • ( ... ) while: A loop that will iterate from i = 0 to the end of the sieve array.
  • dup i a:get: Gets the boolean value at the current index.
  • ( i primes a:push ) if: If the value is 1 (true), it means the index i is a prime number. We push i into our primes result array.
  • drop: After the loop, the original sieve array is still on the stack; we drop it.
  • primes: We push the final primes array onto the stack as the return value.

4. sieve

The main word is a simple composition of the helper words, demonstrating the power of factoring code in 8th. It takes a limit n, initializes the sieve, runs the marking process, collects the results, and leaves the final array of primes on the stack.

Optimizing the Sieve: From Good to Great

The code presented above already includes two of the most critical optimizations. Let's explore why they are so effective.

Optimization 1: Looping Only to the Square Root

In the outer loop, we only check for primes up to sqrt(n) instead of all the way to n. Why is this safe?

Consider a composite number c such that c <= n. This number can be factored into c = a * b. If both a and b were greater than sqrt(n), then their product a * b would be greater than sqrt(n) * sqrt(n), which equals n. This is a contradiction, as we assumed c <= n.

Therefore, for any composite number, at least one of its prime factors must be less than or equal to sqrt(n). By the time our outer loop reaches sqrt(n), we have already found all the necessary prime factors to eliminate every composite number up to n. Any number greater than sqrt(n) that hasn't been eliminated yet must be prime.

Optimization 2: Starting the Inner Loop from i * i

When we find a prime p, we start marking its multiples from p*p, not from 2*p. Why?

Let's take the prime p=5 as an example. The multiples are 10, 15, 20, 25, 30...

  • 2 * 5 = 10: This was already marked when we processed the prime p=2.
  • 3 * 5 = 15: This was already marked when we processed the prime p=3.
  • 4 * 5 = 20: This is not a prime multiple, but it was also marked by p=2.

In general, for any prime p, all its multiples k * p where k < p will have already been marked by a smaller prime factor (specifically, by the prime factors of k). The first multiple of p that has not been marked by any smaller prime is p * p. This simple change significantly reduces the number of redundant write operations to our array, speeding up the algorithm.

This optimization logic is visualized below:

    ● Outer loop finds prime `p`
    │
    ▼
  ┌───────────────────────────┐
  │ Consider multiples of `p`:│
  │ 2*p, 3*p, ..., (p-1)*p    │
  └─────────────┬─────────────┘
                │
                ▼
      ◆ Is `k` in `2..p-1`?
     ╱                    ╲
    Yes                    No (k=p)
    │                      │
    ▼                      ▼
┌──────────────────┐   ┌────────────────────┐
│ `k*p` already has│   │ `p*p` is the first │
│ a smaller prime  │   │ new multiple to    │
│ factor (`k`), so │   │ mark.              │
│ it's already     │   │                    │
│ marked.          │   │ Start inner loop   │
└──────────────────┘   │ here.              │
                       └────────────────────┘
    │
    ▼
    ● Efficiency Gain

Pros and Cons: Sieve of Eratosthenes vs. Trial Division

To appreciate the Sieve's power, it's useful to compare it against the most straightforward method for finding primes: trial division. Trial division checks if a number k is prime by trying to divide it by every integer from 2 up to sqrt(k).

Aspect Sieve of Eratosthenes Trial Division
Time Complexity Excellent: O(n log log n). Very fast for finding all primes in a range. Poor: Roughly O(n * sqrt(n)) to check all numbers up to n. Becomes very slow for large n.
Space Complexity High: O(n). Requires an array of size n, which can be memory-intensive for very large limits. Excellent: O(1). Requires almost no extra memory, as it checks one number at a time.
Use Case Best for generating a list of all primes up to a specific, moderately large limit (e.g., up to 107 or 108). Best for checking if a single, specific number is prime, especially when memory is constrained.
Implementation Slightly more complex due to array management and nested loops. Very simple and straightforward to implement.

The takeaway is clear: if your goal is to generate a list of primes, the Sieve is the superior choice. If you only need to test a few, sparse numbers for primality, trial division might suffice.

Frequently Asked Questions (FAQ)

What is the exact time complexity of the Sieve of Eratosthenes?
The time complexity is O(n log log n). This comes from the sum of operations, which is proportional to n/2 + n/3 + n/5 + ... for all primes up to n. This harmonic series of primes asymptotically approaches n * log(log(n)), making it extremely efficient.

Can the Sieve find primes up to a very large number, like 1012?
Directly, no. The primary limitation of the Sieve is its space complexity of O(n). An array of size 1012 would require terabytes of RAM, which is not feasible for most computers. For such large numbers, more advanced techniques like a segmented sieve (which processes the range in smaller chunks) or probabilistic primality tests like Miller-Rabin are used.

Is the Sieve of Eratosthenes the best algorithm for finding prime numbers?
It depends on the task. For finding all primes up to a limit (up to around 108), it is one of the best and simplest to implement. For larger ranges, the Sieve of Atkin is asymptotically faster, but it is also much more complex to implement correctly. For testing a single large number, probabilistic tests are preferred.

Why is it called a "sieve"?
It's named after the kitchen tool used for sifting. The algorithm works by starting with a list of all numbers and progressively "sifting out" the composite numbers (the multiples). The numbers that remain—that don't fall through the sieve—are the prime numbers.

How does this algorithm relate to modern technology trends?
Understanding fundamental algorithms like the Sieve is crucial for performance engineering in any language. As we move towards more data-intensive applications and distributed computing, the ability to analyze and optimize for time and space complexity is a vital skill. The logic behind the Sieve is a masterclass in trading space for time, a common paradigm in high-performance computing.

Can this logic be implemented in other languages?
Absolutely. The logic is language-agnostic. You can implement the Sieve of Eratosthenes in Python, Java, C++, Rust, Go, or any other language that supports arrays and loops. The core principles of creating a boolean array and marking multiples remain identical. You can explore more implementations in our other guides, such as our complete 8th language guide.

Conclusion: The Enduring Legacy of an Ancient Algorithm

The Sieve of Eratosthenes is more than just a historical curiosity; it is a testament to timeless algorithmic elegance. By starting with a simple assumption—that all numbers are prime—and methodically eliminating the exceptions, it provides a fast and intuitive way to map the foundational building blocks of mathematics. Implementing it, as we have in the 8th language, reinforces core programming concepts like array manipulation, looping, and the critical importance of optimization.

Whether you're benchmarking a garage sale computer, preparing for a coding competition, or delving into the world of number theory, the Sieve is an indispensable tool in your intellectual arsenal. It serves as a powerful reminder that sometimes, the most effective solutions are the ones that have been refined over millennia.

To continue your journey and tackle more challenges like this, be sure to explore the complete 8th learning path on kodikra, where you can find a structured curriculum designed to take you from novice to expert.

Disclaimer: The 8th code in this article is written to be clear and educational, adhering to the principles of the language. Implementations may vary based on the specific version of the 8th interpreter or compiler you are using.

Published by Kodikra — Your trusted 8th learning resource.

Post a Comment