How Do You Find Every Prime Under a Million? Cross Out the Rest

Write out the whole numbers from two upwards to whatever limit is wanted. Take the first number not yet crossed out, which is two, and cross out every multiple of it beyond itself, removing all the even numbers. Move to the next surviving number, which is three, and cross out every multiple of that. The next survivor is five, since four has gone, and the process repeats. Each surviving number in turn is prime, because if it had any smaller factor it would already have been crossed out as a multiple of that factor. Once the working number exceeds the square root of the limit, everything remaining is prime and the work is finished.

The advantage lies in how the work is distributed:

• •Testing one number for primality requires trying many possible divisors
• •Crossing out multiples requires only repeated addition, which is trivial
• •Each composite number is crossed out once for each of its prime factors
• •The total work grows only slightly faster than the size of the list
• •Stopping at the square root of the limit removes most of the remaining work
• •Crossing out can begin at the square of each prime, since smaller multiples are already gone

The method is attributed to Eratosthenes, a Greek scholar working in Alexandria in the third century before the common era, who is better known for measuring the circumference of the Earth from the difference in shadow lengths between two cities. The attribution comes from a later source rather than from any surviving work of his own, so the credit is traditional rather than documented. The name reflects the image of a sieve retaining the primes while composites fall through. Its survival for over two thousand years without fundamental improvement is unusual in mathematics and reflects that the approach is close to optimal for the task.

Running the procedure and looking at what survives reveals patterns that have occupied mathematicians for centuries. The primes thin out as numbers grow, at a rate that is precisely described, with the proportion of numbers below a given size that are prime falling roughly in proportion to the logarithm of that size. Despite thinning, they never run out, which Euclid proved by an argument that needs no computation at all. Pairs differing by two keep appearing far out into enormous numbers, and whether they continue forever is unproven. Long runs with no primes at all can be constructed deliberately of any length wanted. The sieve makes all of this visible immediately, which is part of why it is the standard first computational exercise in the subject.

The method is fast and is limited by memory rather than by time, which determines how it is used in practice. Listing primes up to a billion requires marking a billion positions, which fits comfortably in a modern computer, and listing them up to a very large limit does not, since the whole range must be held at once. Segmented versions address this by processing the range in blocks, keeping only the small primes up to the square root permanently and sweeping each block in turn, which reduces memory enormously at no cost in speed. For determining whether one enormous number is prime, sieving is useless and entirely different methods are used, which is the situation in cryptography where numbers of hundreds of digits are involved.

Writing out every number and crossing out multiples of each survivor leaves the primes, because anything with a smaller factor has already gone. Crossing out needs only addition while testing one number needs many divisions, and the work stops at the square root of the limit. The method is attributed to Eratosthenes in the third century before the common era and has never been fundamentally improved.