This site is supported by donations to The OEIS Foundation.

From OeisWiki

The sieve of Eratosthenes is a simple algorithm dating from Greek antiquity giving all the prime numbers (Cf. A000040) up to a specified integer in a rectangular array, by identifying the primes one by one and crossing off their multiples. Often it is presented as a 10 × 10 array showing the 25 primes up to 100.

It is especially convenient to have 30 numbers per row since 30 = 2 × 3 × 5 is a primorial number with a good size for a table, the previous primorial number 6 = 2 × 3 being rather too small and the next primorial number 210 = 2 × 3 × 5 × 7 being rather too large for a table. Excluding the prime factors of 30 (2, 3, 5), since there are eight congruences (mod 30) which are relatively prime to 30 (i.e. ^[1],) the congruence classes {1, 7, 11, 13, 17, 19, 23, 29} (mod 30) or equivalently {±1, ±3, ±7, ±11} (mod 30), any other prime may only appear among those.

We need only apply the sieving algorithm for primes up to , thus for a square array like 30 × 30, we need only consider the primes from the first row for the sieving process.

Note that apart from the twin prime pairs {3, 5} and {5, 7}, any other twin prime pairs must be among the congruence pairs {0±1}, {12±1} and {18±1} (mod 30). Also, apart from the cousin prime pair {3, 7}, any cousin prime pairs must be among the congruence pairs {9±2}, {15±2} and {21±2} (mod 30). (See prime constellations)

Since the odd numbers are in arithmetic progression, the sieve of Eratosthenes algorithm may be applied to the odd numbers only, saving half the space.

Table of sieved integers

The sieving algorithm

A. Write a range of integers in order into an array, usually starting with 1.

B. Choose a small prime, usually .

C. Circle or highlight and cross out its square and all its higher multiples that haven't already been crossed off. (Note that 4 is crossed out, it just happens to fall on the horizontal bar of the numeral 4.)

D. Whichever number is to the right of (or leftmost on the next row) that hasn't been crossed off ought to be a prime. Circle or highlight it: it has now become . If is within the array, repeat Step C with the new . Otherwise, you're done.

...

Number of primes less than or equal to 2^(2^n)

A153450 Number of primes <= 2^(2^n) = PiPrime(A001146), n >= 0.

{1, 2, 6, 54, 6542, 203280221, ...}

The primes up to are exactly determined from the primes up to with the sieve of Eratosthenes. This gives an inductive algorithm to find all primes up to any integer (modulo space and time constraints...) This means that all odd primes are ultimately determined by the only even prime, namely 2, the oddest prime...

The primes less than or equal to where each subset is exactly determined by the preceding subset, are

{{2}, {2, 3}, {2, 3, 5, 7, 11, 13}, {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251}, ...}

Sequences

Squares of prime numbers (Cf. A001248)

{4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609, 11449, 11881, 12769, 16129, 17161, 18769, 19321, 22201, ...}

In doing the sieve of Eratosthenes, this sequence gives the first composite number that you'll cross off after you identify the ^th prime (that is, unless you like to cross off again the composite numbers that have already been crossed off for a smaller prime factor – e.g., for the third prime, 5, the first number to cross off is 25, because 10, 15 and 20 should have already been crossed off for 2, 3 and 2 respectively.

In the following sequences, refers to the primorial of .

Result of first stage of sieve of Eratosthenes (after eliminating multiples of 2) (). (Cf. A004280)

{1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, ...}

Result of second stage of sieve of Eratosthenes (after eliminating multiples of 2 and 3) (). (Cf. A038179, except first term)

{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, ...}

Result of third stage of sieve of Eratosthenes (after eliminating multiples of 2, 3 and 5) (). (Cf. A054403, except first term)

{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 133, 137, 139, 143, 149, 151, 157, 161, 163, 167, ...}

Result of fourth stage of sieve of Eratosthenes (after eliminating multiples of 2, 3, 5, 7) (). (Cf. A055398, except first term)

{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, ...}

Result of fifth stage of sieve of Eratosthenes (after eliminating multiples of 2, 3, 5, 7, 11) (). (Cf. A??????, except first term?)

{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, ...}

Result of sixth stage of sieve of Eratosthenes (after eliminating multiples of 2, 3, 5, 7, 11, 13) (). (Cf. A??????, except first term?)

{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, ...}

See also

• Index entries for sequences generated by sieves
• Lucky numbers (generated by a different sieving algorithm)
• Ulam spiral

Notes

1. ↑ Cf. Euler's totient function.