Sieve of Eratosthenes

The sieve of Eratosthenes is a famous mathematical algorithm used to find all prime numbers up to a specific limit. A prime number is a natural number with exactly two distinct divisors: 1 and itself. Finding these numbers can be difficult as they become more spread out among larger integers. This method is highly efficient for discovering smaller primes because it identifies composite numbers through a systematic process. Instead of testing each number individually, the sieve works by removing non-prime numbers from a list.

To understand the mechanism, imagine a list of consecutive integers starting from 2 up to your chosen limit, $n$. You begin with the smallest prime, which is 2. You then mark every multiple of 2 in the list, such as 4, 6, and 8, as composite. These are numbers that are not prime. Next, you look for the smallest unmarked number greater than 2, which is 3. You then mark all multiples of 3, such as 6, 9, and 12. You continue this process iteratively. Each time you find an unmarked number, it is guaranteed to be prime. You then mark its multiples until you reach your limit.

There are several ways to refine this process to make it faster. One common optimization is to start marking multiples from the square of the prime. For example, when you reach the prime 5, you can start marking at 25. This works because all smaller multiples, like 10 or 15, were already marked by smaller primes like 2 or 3. Another optimization allows the algorithm to stop early. You only need to continue the process as long as the square of your current prime is less than or equal to $n$. Once the square of the next prime exceeds $n$, all remaining unmarked numbers in your list are prime.

This method has a long history in mathematics. It is attributed to Eratosthenes of Cyrene, a Greek mathematician from the 3rd century BCE. The earliest known written reference to the sieve appears in the book "Introduction to Arithmetic" by Nicomachus of Gerasa. This book was written in the early 2nd century CE. While Nicomachus described a version using odd numbers, the core idea remains the same. The sieve has remained a fundamental tool for mathematicians for thousands of years.

Modern computer science uses different versions of this idea to handle massive numbers. A standard sieve can require a lot of memory if the limit $n$ is very large. To solve this, mathematicians use a segmented sieve. This version divides the range of numbers into smaller segments or "pages." You find the primes in the first segment using the regular method. Then, you use those primes to mark composites in each subsequent segment. This approach significantly reduces the amount of memory needed.

Another variation is the incremental sieve, which can generate primes indefinitely without a set upper bound. It works by interleaving the generation of primes with the generation of their multiples. This allows you to find primes in the gaps between multiples as they appear. While some people confuse this with trial division, they are different. Trial division tests if a number is divisible by primes one by one. In contrast, the sieve of Eratosthenes directly generates the composite numbers. This makes the sieve much more efficient for finding ranges of primes.

In terms of complexity, the sieve is a useful way to benchmark computer performance. The time complexity for calculating primes up to $n$ is $O(n \log \log n)$. This is a very efficient rate of growth. However, the basic algorithm requires $O(n)$ memory to store the list of numbers. This is why segmented versions are so important for large-scale calculations. The sieve remains one of the most important bridges between ancient arithmetic and modern computational number theory.