The Sieve of Eratosthenes

The Sieve of Eratosthenes^[1] is an ancient, deterministic algorithm used in mathematics and computer science to find all prime numbers up to a specified integer limit.^[32][33] By iteratively marking the multiples of each discovered prime as composite, the algorithm isolates the remaining unmarked numbers as primes.^[34] It operates on the fundamental principle of arithmetic, which dictates that any composite number can be factored into smaller primes. Consequently, systematically crossing out the multiples of known primes will inevitably leave only the prime numbers behind.

Unlike trial division, which tests each candidate number individually for divisibility by smaller integers, the sieve processes the entire range of numbers concurrently. This batch processing approach avoids the overhead of repeated division operations, relying instead on simple addition to traverse an array of candidates. The algorithm begins with the first prime number, 2, and marks all of its subsequent multiples. It then advances to the next unmarked number, which is guaranteed to be prime, and repeats the marking process. This continues until the algorithm has processed all necessary base primes, at which point the sieve is complete.

The algorithm is named after Eratosthenes of Cyrene, a Greek mathematician, geographer, and polymath who lived in the third century BC.^[34] Although his original writings on the subject are lost to history, the method was preserved and attributed to him by later scholars. Today, the Sieve of Eratosthenes remains a foundational concept in algorithmic number theory^[2].^[35] It serves as the basis for highly optimized prime generation routines in modern software, ranging from computer algebra systems to cryptographic key generation utilities. Its continued relevance stems from its mechanical simplicity, which aligns perfectly with the architecture of modern microprocessors.

Algorithmic Mechanism and Complexity

To execute the Sieve of Eratosthenes up to a given limit $n$, the algorithm requires a contiguous block of memory to represent the integers from 2 to $n$. This is typically implemented as an array of Boolean values, where each index corresponds to an integer, and the value at that index indicates whether the number is potentially prime.

The algorithm proceeds through the following steps:

1. Initialize an array of Boolean values from 2 to $n$, setting all entries to true.
2. Set the current number $p$ to 2, the smallest prime number.
3. Iterate through the array in increments of $p$, starting from $p^2$, and mark each visited index as false (composite).
4. Find the next index greater than $p$ that is still marked as true. If no such index exists, or if $p^2 > n$, the algorithm terminates.
5. Update $p$ to this new index and repeat step 3.

algorithm SieveOfEratosthenes is
    input: an integer n > 1
    output: all prime numbers from 2 to n

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.

    for i = 2, 3, 4, ..., not exceeding floor(sqrt(n)):
        if A[i] is true:
            for j = i^2, i^2 + i, i^2 + 2i, ..., not exceeding n:
                A[j] := false

    return all i such that A[i] is true

Two mathematical optimizations are standard in any practical implementation. First, the inner loop that marks multiples of $p$ begins at $p^2$ rather than $2p$. Any multiple of $p$ smaller than $p^2$ can be expressed as $p \times q$ where $q < p$. Since $q$ is smaller than $p$, this composite number would have already been marked as false during the iteration when $q$ (or one of its prime factors) was processed. For example, when $p = 5$, the multiples 10, 15, and 20 are already marked by the time the algorithm processes 5, allowing the marking to safely begin at 25.

Second, the outer loop only needs to continue until $p$ exceeds $\lfloor\sqrt{n}\rfloor$. If a number $k \le n$ is composite, it must have at least one prime factor less than or equal to $\sqrt{n}$. If all primes up to $\sqrt{n}$ have had their multiples marked, all composite numbers in the entire array up to $n$ will have been crossed out.

The time complexity of the Sieve of Eratosthenes is $O(n \log \log n)$ in the Random Access Machine model. The outer loop finds primes, and the inner loop executes $n/p$ times for each prime $p$. The total number of operations is proportional to $n \sum_{p \le \sqrt{n}} \frac{1}{p}$. According to Mertens' second theorem^[3], the sum of the reciprocals of the primes up to $x$ grows asymptotically as $\log \log x$. Therefore, the total time complexity is bounded by $O(n \log \log n)$. This makes the algorithm highly efficient, performing only slightly more than linear time. The divergence of the harmonic series of primes is extremely slow, meaning that for all practical computing limits, $\log \log n$ acts almost as a constant. Furthermore, the predictable branching of the inner loop makes the algorithm highly compatible with modern CPU branch predictors, ensuring that the instruction pipeline rarely stalls.

The primary limitation of the basic algorithm is its space complexity, which is $O(n)$ bits. For very large values of $n$, the memory required to store the Boolean array exceeds the capacity of the CPU cache, leading to frequent cache misses and degraded performance. In practical software implementations, the Boolean array is rarely implemented as an array of bytes. Instead, programmers use bit packing, where each bit within a 32-bit or 64-bit machine word represents a single integer. Since the only even prime is 2, the array can be optimized to only store the state of odd numbers. The number $2k+1$ is mapped to the $k$-th bit of the array. This halves the memory requirement immediately. Combined with bit packing, the memory footprint is reduced by a factor of 16 compared to a naive byte array. The inner loop then involves calculating the word index via integer division and the bit offset via modulo arithmetic, followed by applying a bitwise AND or OR operation to clear or set the specific bit.

Historical Origins and Preservation

Eratosthenes of Cyrene^[4] (c. 276 to 194 BC) was a Greek mathematician, geographer, and astronomer. Born in Cyrene (in modern Libya) and educated in Athens, he was invited to Egypt by Ptolemy III Euergetes to serve as the chief librarian at the Library of Alexandria. The library was the intellectual center of the ancient Mediterranean, providing Eratosthenes with the resources to make massive contributions to multiple fields. He is most famous for calculating the circumference of the Earth with remarkable accuracy, but he also made significant contributions to number theory.^[33] Eratosthenes developed his sieving method as a systematic way to isolate prime numbers, which were of great interest to Greek mathematicians studying divisibility and perfect numbers.

None of Eratosthenes' original mathematical manuscripts have survived the destruction of the Library of Alexandria and the general decay of ancient texts. The algorithm is known today entirely through the writings of Nicomachus of Gerasa, a Neopythagorean philosopher who lived in the early second century AD. In his work Introduction to Arithmetic (Arithmetike eisagoge), Nicomachus described the algorithm in detail and explicitly attributed it to Eratosthenes. Nicomachus framed the algorithm slightly differently than modern implementations; he suggested writing out the sequence of odd numbers and then systematically crossing out multiples of 3, 5, 7, and so on. This early optimization of ignoring even numbers demonstrates that the conceptual mechanics of the sieve were well understood in antiquity.

The text of Introduction to Arithmetic was highly influential and served as a standard mathematical textbook in the ancient and medieval worlds. It was translated into Latin by Boethius in the sixth century and later translated into Arabic, ensuring that the Sieve of Eratosthenes was preserved through the Middle Ages and transmitted to Renaissance mathematicians. The preservation of this algorithm highlights the interconnected nature of historical mathematics, where Greek concepts were maintained and studied by Islamic and European scholars until the advent of mechanical and electronic computing provided a new medium for their execution.

Algorithmic Refinements and Variants

While the basic Sieve of Eratosthenes is efficient, centuries of mathematical and computational research have produced numerous refinements to reduce its time and space complexity, as documented in systematic reviews of prime sieving^[5].^[36]

Linear Time Sieves

The standard sieve touches some composite numbers multiple times. For instance, the number 30 is marked as a multiple of 2, 3, and 5. Leonhard Euler formulated this method in 1737 (published in 1744) in his proof of the Euler product formula, $O(n)$, by ensuring that each composite number is crossed out exactly once. Modern linear sieves, such as those published by David Gries and Jayadev Misra in 1978^[6] and Harry Mairson in 1977^[7], achieve this by maintaining a list of discovered primes.

The linear sieve relies on the fundamental theorem of arithmetic. Every composite number $C$ can be uniquely factored as $C = p \times x$, where $p$ is the smallest prime factor of $C$, and $x \ge p$. As the algorithm iterates through each integer $x$ from 2 to $n$, if $x$ is unmarked, it is added to the prime list. Then, regardless of whether $x$ is prime or composite, the algorithm iterates through the prime list, multiplying $x$ by each prime $p$ to compute $C = p \times x$, and marking $C$ as composite. The inner loop terminates early if $x$ is divisible by $p$. This early termination condition guarantees that each composite number is generated and marked exactly once. While mathematically elegant, the requirement to maintain a dynamic list of primes and perform integer multiplication makes this approach slower in practice than the standard sieve for typical ranges. The constant factor introduced by multiplication and complex memory access patterns outweighs the asymptotic advantage of $O(n)$ over $O(n \log \log n)$.

Segmented Sieve

To address the $O(n)$ memory requirement, Carter Bays and Richard H. Hudson published the segmented sieve of Eratosthenes in 1977^[8]. Instead of allocating a single array of size $n$, the segmented sieve divides the range $[2, n]$ into smaller blocks or segments of a fixed size $\Delta$. The algorithm first computes all base primes up to $\sqrt{n}$ using the standard sieve. Then, for each segment, it uses these base primes to mark the composites within that specific range. Similar block techniques were utilized by Richard P. Brent in 1973^[9] to compute large gaps between successive primes.

To illustrate the segmented sieve, consider finding primes in the range from 100 to 120. The square root of 120 is approximately 10.95, so the required base primes are 2, 3, 5, and 7. The algorithm allocates a small array representing the numbers 100 to 120. For the prime 2, the first multiple in the range is 100, so it marks 100, 102, 104, and so on. For the prime 3, the first multiple is 102, marking 102, 105, 108, etc. Once all base primes have been applied to the segment, the unmarked numbers (101, 103, 107, 109, 113) are identified as prime.

The space complexity of the segmented sieve is $O(\sqrt{n} + \Delta)$. By choosing $\Delta \approx \sqrt{n}$, the memory footprint is reduced to $O(\sqrt{n})$. In modern computing, $\Delta$ is typically chosen to fit entirely within the CPU's Level 1 (L1) data cache, which is usually between 32 kilobytes and 64 kilobytes. Main memory latency is typically hundreds of clock cycles, whereas L1 cache latency is only a few clock cycles. By keeping the working set entirely within the L1 cache, the segmented sieve ensures that the memory accesses during the inner loop are nearly instantaneous, virtually eliminating the RAM latency bottleneck that affects the unsegmented sieve. Recent research into the space complexity of prime sieves (2024)^[10] has demonstrated methods to further compress the required space to $O(\sqrt{n} / \log \log n)$ bits while maintaining optimal running time.

Wheel Factorization and Pritchard's Sieve

Wheel factorization^[11] is an optimization that skips multiples of small primes entirely. A "wheel" is formed by taking the primorial (the product of the first $k$ primes). For example, a wheel for the primes 2, 3, and 5 has a circumference of $2 \times 3 \times 5 = 30$. Out of the 30 integers in this cycle, only 8 are coprime to 2, 3, and 5. By only storing and processing numbers that align with these 8 positions, the sieve immediately reduces its workload and memory usage by a factor of $30/8 = 3.75$.

In 1981, Paul Pritchard introduced a sublinear additive sieve^[12], often called the Sieve of Pritchard or the dynamic wheel sieve. Pritchard's algorithm dynamically builds larger wheels as it progresses, effectively sieving out composites without ever explicitly considering them. This reduces the time complexity to $O(n / \log \log n)$, making it the first prime sieve to achieve a sublinear running time relative to the range size. Pritchard later expanded on the mathematical framework of this algorithm in his 1982 paper, Explaining the wheel sieve^[13].

Incremental Sieves

Standard sieves require the upper bound $n$ to be known in advance. Incremental sieves generate primes indefinitely without a fixed upper bound. S. Bengelloun published an incremental primal sieve in 1986^[14], and modern functional programming languages often implement lazy, incremental sieves, as detailed by Melissa O'Neill in The Genuine Sieve of Eratosthenes^[15]. O'Neill demonstrated that naive recursive implementations in languages like Haskell often devolve into trial division rather than true sieving. To restore the efficiency of Eratosthenes, she proposed using a priority queue to track the next multiples of discovered primes. More recently, algorithms for compact incremental prime sieves have been developed that operate in $O(n \log \log n)$ time while using only $O(\sqrt{n} \log n)$ bits of space.

Sieve of Sundaram

Discovered by Indian mathematician S. P. Sundaram in 1934, the Sieve of Sundaram^[16] is a deterministic variant that operates purely on arithmetic progressions. It begins with a list of integers from 1 to $m$, where $m = \lfloor(n-1)/2\rfloor$. It then removes all numbers of the form $i + j + 2ij$, where $i$ and $j$ are integers such that $1 \le i \le j$ and $i + j + 2ij \le m$. The remaining numbers in the list are doubled and incremented by one to produce all odd primes up to $n$. The algebraic identity $(2i+1)(2j+1) = 4ij + 2i + 2j + 1 = 2(i + j + 2ij) + 1$ guarantees that this process exactly eliminates the odd composite numbers.

Sieve of Atkin

Published in 2004 by A. O. L. Atkin and Daniel J. Bernstein, the Sieve of Atkin^[17] is a modern algorithm that uses binary quadratic forms rather than simple multiples. Instead of crossing out multiples, the algorithm toggles the boolean state of a number based on the number of solutions to specific quadratic equations (such as $4x^2 + y^2 = n$). The rules for which equation to use depend on the modulo 60 remainder of $n$. The Sieve of Atkin achieves a theoretical time complexity of $O(n / \log \log n)$ and a space complexity of $O(n^{0.5 + o(1)})$. While theoretically superior, the Sieve of Atkin involves complex modulo arithmetic and state toggling, meaning that a highly optimized segmented Sieve of Eratosthenes often outperforms it in practice for limits below $10^{10}$, as noted in Crandall and Pomerance's Prime Numbers: A Computational Perspective^[18]. The original methodology is detailed in Atkin and Bernstein's paper, Prime sieves using binary quadratic forms^[19].

Parallelization and Modern Hardware Adaptation

As microprocessor clock speeds plateaued in the early 21st century, software performance improvements became heavily dependent on parallel computing and memory hierarchy optimization. The Sieve of Eratosthenes, particularly in its segmented form, is exceptionally well suited to modern multicore processors and graphics processing units.

The segmented sieve is classified as an embarrassingly parallel algorithm. Once the initial set of base primes up to $\sqrt{n}$ is computed, the remaining segments of the array can be processed entirely independently. There is no data dependency between the first segment and the second segment; a thread processing the range from 100,000 to 110,000 does not need to communicate with a thread processing the range from 110,000 to 120,000. This allows the algorithm to scale almost linearly with the number of available processor cores. Early research into this capability was documented in Shahid H. Bokhari's 1987 paper, Multiprocessing the Sieve of Eratosthenes^[20], which analyzed the algorithm's performance on early parallel architectures.

In modern implementations, parallelization is typically achieved using application programming interfaces like OpenMP or POSIX threads. A master thread computes the base primes and then dispatches chunks of the search space to worker threads. Because each thread allocates its own local memory block for its assigned segment, the algorithm avoids the performance penalty of false sharing. False sharing occurs when multiple threads modify variables that reside on the same cache line, forcing the CPU to constantly invalidate and reload the cache across cores. By ensuring that each thread works on a disjoint memory segment, the segmented sieve maximizes cache coherence and overall throughput.

Highly tuned software libraries, such as Kim Walisch's primesieve^[21], combine these parallelization techniques with extreme cache optimization. Such implementations use bucket sieving to manage the multiples of large primes that do not frequently strike within a small segment, ensuring that the L1 data cache is utilized with maximum efficiency. Similar adaptations have been made for graphics processing units using frameworks like CUDA, where thousands of lightweight threads concurrently apply base primes to massive arrays in device memory.

Real-World Applications and Implementations

The Sieve of Eratosthenes and its variants are heavily utilized in modern computational infrastructure, particularly where bulk prime generation is required.

Cryptography

Public key cryptography standards, such as those defined by Rivest, Shamir, and Adleman (RSA)^[22], require the generation of large prime numbers. For a 2048-bit RSA key, the system must generate two 1024-bit primes to form the modulus. Finding these primes involves generating random large odd numbers and testing them for primality. Because rigorous primality tests like the Miller-Rabin test are computationally expensive, cryptographic libraries first use a small Sieve of Eratosthenes to generate a list of primes up to a few thousand. The large candidate number is subjected to trial division against this precomputed list. If it is divisible by any of these small primes, it is immediately discarded, saving the CPU cycles that would have been wasted on a full probabilistic test. Trial division against a sieved list of primes up to 65,536 eliminates over 90 percent of random odd numbers before they ever reach the Miller-Rabin test. This hybrid approach is specified in standards such as RFC 8017^[23] and the National Institute of Standards and Technology's FIPS 186-5^[24] standard for digital signatures.

In cryptographic applications like the Diffie-Hellman key exchange, protocols often require safe primes. A safe prime is a prime number of the form $2p + 1$, where $p$ is also a prime. Generating these numbers requires finding a sequence of related primes. Sieving techniques are heavily utilized here; a modified Sieve of Eratosthenes can simultaneously track the primality of $k$ and $2k+1$, rapidly eliminating candidates where either value is composite. This drastically reduces the search space before the computationally heavy probabilistic tests are invoked.

Computer Algebra Systems

Mathematical software and computer algebra systems, including the PARI/GP Computer Algebra System^[25], SageMath^[26], and the GNU Multiple Precision Arithmetic Library (GMP), rely heavily on the segmented sieve of Eratosthenes. These systems frequently need to compute the prime counting function^[27] $\pi(x)$, factorize medium-sized integers, or search for prime constellations like twin primes.^[35] GMP implements a highly tuned segmented sieve with wheel factorization, utilizing bit-level parallelism and assembly-optimized inner loops to maximize throughput.

Benchmarking

In the early era of microcomputing, the Sieve of Eratosthenes became a standard benchmark for evaluating the performance of compilers, interpreters, and microprocessors. In September 1981, Jim Gilbreath published an article in BYTE magazine^[28] detailing a benchmark based on the sieve, which became known as the "Byte Sieve". Gilbreath chose the algorithm because it required no hardware multiplication or division instructions, which were either absent or extremely slow on 8-bit processors like the Z80 and 6502. Instead, the Byte Sieve stressed the processor's ability to perform array lookups, memory addressing, and basic branching. It remained a standard industry benchmark throughout the 1980s, and its utility in performance testing was further analyzed in Reinhold P. Weicker's 1990 paper, An overview of common benchmarks^[29].

Significance and Tradeoffs

The utility of the Sieve of Eratosthenes stems from its extreme simplicity and its low constant factors. For generating all primes up to a limit $n$, it is mathematically impossible to do less work than identifying the status of each number, and the sieve approaches this theoretical minimum with operations that are native and fast on modern CPUs. The algorithm is extensively analyzed in foundational computer science texts, including Donald Knuth's The Art of Computer Programming^[30] and Jonathan Sorenson's An Introduction to Prime Number Sieves^[31].

The algorithm is strictly a range generation tool. It is entirely unsuited for determining the primality of a single, isolated large number. If one needs to know whether a specific 100-digit number is prime, building a sieve up to that number is physically impossible, as it would require more memory than exists in the universe. In such cases, probabilistic primality tests or the deterministic AKS primality test are required.

While sublinear sieves like the Sieve of Pritchard and the Sieve of Atkin offer better asymptotic time complexity, they introduce significant overhead in control flow and arithmetic complexity. The standard segmented sieve of Eratosthenes, augmented with a small wheel, maps directly to the hierarchical cache architecture of modern processors. The inner loop consists of a single pointer increment and a bitwise OR operation, which compilers can aggressively unroll and vectorize. As a result, the ancient algorithm, adapted for cache locality, remains the fastest known method in practice for generating prime numbers up to $10^{12}$.