Beginning Java Data Structures and Algorithms

Sieve of Eratosthenes

The sieve of Eratosthenes is a simple and ancient algorithm to find all prime numbers up to a given limit. If we want to find all prime numbers up to N, we start by creating a list of consecutive integers from 2 to N (2, 3, 4, 5… N), initially unmarked. Let's use p to denote the smallest unmarked number. Then, we select the smallest unmarked number p that is larger than the last p. In the first iteration, p will be two. Afterwards, by increments of p, we mark elements in the list from 2p until Mp so that Mp <= N.

We repeat this strategy until it is impossible to mark more numbers in the list. At the end of the run, all the unmarked numbers are prime numbers. It is easy to see that all unmarked numbers will be the ones ...