How the Sieve of Eratosthenes Finds Prime Numbers

A prime number has exactly two positive divisors: 1 and itself. Primes are the building blocks of all whole numbers, and finding them is one of the oldest problems in mathematics. The sieve of Eratosthenes is a simple method for listing every prime up to a chosen limit, and it has been taught for more than two thousand years because its idea is so clear.

This guide explains the steps, works an example up to 50, explains why the method can stop early, and describes how fast it runs.

The core idea

Instead of testing each number for primality directly, the sieve removes numbers that cannot be prime. Start with a list of all integers from 2 up to your limit. Any number that is a multiple of a smaller prime must be composite, because it has that prime as a divisor. So you cross out multiples, and whatever survives must be prime.

The method is named after Eratosthenes of Cyrene, a Greek scholar who lived around the third century BCE. The name refers to the sieve as a filter that lets the primes through and holds back the rest.

The steps

First, write down every integer from 2 up to your limit N. Second, find the smallest number that is not crossed out. That number is prime. Third, cross out every multiple of that prime, starting from its square, because smaller multiples were already crossed out by earlier primes. Fourth, repeat from step two until no further primes need testing. Every number left uncrossed is prime.

A worked example up to 50

Start with the numbers 2 through 50. The first uncrossed number is 2, so 2 is prime. Cross out its multiples: 4, 6, 8, and so on, every even number above 2.

The next uncrossed number is 3, so 3 is prime. Cross out its multiples: 6, 9, 12, 15, and so on. Many of these were already removed by 2, but the rule still applies.

The next uncrossed number is 5, so 5 is prime. Cross out 10, 15, 20, 25, and so on. Then 7 is prime, and you cross out 14, 21, 28, 35, 42, and 49.

Once you have processed the primes up to 7, every composite number up to 50 has been removed. The surviving numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47. That is fifteen primes.

Why you can stop at the square root

You do not need to test primes all the way up to N. If a composite number has no prime factor up to its square root, it cannot exist, because a composite number always has a factor no larger than its square root. For example, any composite number at most 50 has a prime factor at most the square root of 50, which is about 7.07. So after you process 7, the job is finished.

This shortcut is why the sieve is so efficient. Rather than crossing out every multiple of every prime, it only starts each prime's crossing-out at that prime's square. The multiples below the square were already removed by smaller primes.

How the count grows

The number of primes up to N is written pi of N. The table uses known values to show how it grows as the limit increases.

Limit N	Primes up to N	Share of numbers that are prime
10	4	40 percent
100	25	25 percent
1,000	168	16.8 percent
10,000	1,229	12.3 percent

The count keeps rising, but the share of primes keeps falling. Primes become rarer as numbers get larger, although they never run out.

How fast the sieve runs

The sieve performs roughly N times log log N operations, where log log N is the logarithm of the logarithm of N. For practical purposes that grows only a little faster than linear, which makes the method fast for lists of millions of numbers.

The main cost is memory. A straightforward sieve needs an array of N flags, one per number. For a limit of one billion, that array is large, so practical implementations use bit arrays, which store one bit per number, or segmented sieves, which process the range in blocks that fit in memory.

Comparing with trial division

The simplest primality test is trial division. To check a single number, divide it by every prime up to its square root, and if none divides it evenly, the number is prime. Testing 47 this way needs only the primes 2, 3, and 5, because the square root of 47 is about 6.86. Testing every number up to 50 by trial division gives the same list as the sieve, but it repeats the same divisions many times over.

The sieve trades that repetition for a table. It spends its effort once, crossing out composites in bulk, and then reads the answer off the table. When you need every prime in a range, the table wins. When you need to test one isolated number, trial division or a probabilistic test is usually the better choice.

Where the sieve is used

The sieve is the standard way to produce a list of small primes. Many other algorithms need a supply of primes, including the trial division steps in factoring algorithms and the generation of test values for primality tests.

It is not the tool for testing one very large number. To check whether a single enormous number is prime, mathematicians and software use probabilistic tests such as the Miller-Rabin test, or deterministic tests for limited ranges. Those tests do not require a full list of primes.

Cryptography depends on large primes, but the sieve is still useful there, because it quickly removes small factors from candidate numbers before the expensive tests run.

Common misunderstandings

The first misunderstanding is that 1 is prime. It is not. A prime must have exactly two divisors, and 1 has only one, so the sieve starts at 2.

The second is that the sieve finds primes by checking divisibility of each number by every smaller number. That approach is much slower. The sieve avoids it by crossing out multiples in bulk.

The third is that the sieve must always go past the square root. Once the squares exceed the limit, every remaining uncrossed number is prime, so further steps add no new information.

Key takeaways

The sieve of Eratosthenes lists all primes up to a limit by starting with every integer, repeatedly taking the next uncrossed number as prime, and crossing out its multiples. Whatever remains at the end is prime.

The method stops once the primes reach the square root of the limit, and its speed comes from crossing out multiples in bulk rather than testing each number separately. It is the standard way to build a table of small primes.