Burnt Jet Homepage   
Search Site: Enter text and press 'Search Site' to find relevant items within this site, starting at the selected location. Location: Select location within this site to start the search from.


Prime Number Sieves

Demonstration Sieve (Euler's algorithm)

Key: initial; prime; not prime.

Integers 1 to 100 (10 x 10 grid)
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

These prime number sieve's are algorithms for determining which numbers in the integer sequence 1 to N are prime.

Contents

  1. Sieve of Eratosthenes
  2. Euler's Sieve
  3. Limitations

Sieve of Eratosthenes

Eratosthenes (276-194 B.C.) was a librarian in the library of Alexandria. He is known for determining the circumference of the Earth and estimating the distances to the sun and the moon. He is also credited (in the Introduction to Arithmetic by Nicomachus) for an algorithm to determine the prime numbers in the sequence of integers 1 to N, where N is a larger positive integer. This algorithm is known as the "Sieve of Eratosthenes" because it sequentially filters out the multiples of known primes as therefore being non-prime.

To find all prime numbers below a given number N:

  1. Write all integers from 1 through N in order;
  2. Eliminate 1 as it is a not a prime number by definition;
    Alternatively (commonly), skip step 2 by omitting the integer 1 when initialising the list with integers 2..N;
  3. Repeat the following steps until the next found prime is greater than the square root of N;
    • find the next number not yet eliminated (initially 2, then 3, then 5, etc.);
    • mark this number as prime;
    • eliminate all of its remaining multiples (means checking for multiples already eliminated);

All the non-eliminated numbers in the list must be prime.

Euler's Sieve

Euler improved on the sieve of Eratosthenes, so that each number is eliminated exactly once - see demonstration of Euler's Sieve (everyone does the Sieve of Eratosthenes demo).

  1. Start with all the natural (positive integer) numbers greater than 1, because 1 is not a prime:
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...
    ^
  2. The leftmost number is prime. Multiply each number in the list by this prime and discard the products (2x2, 2x3, 2x4, 2x5, etc.):
    2 3   5   7   9    11    13    15    17    19    21    23    25    27    29    31    33    35...
      ^
  3. The number after the previous prime is also a prime. Multiply each number in the list starting from the latest prime by the latest prime and discard the products (3x3, 3x5, 3x7, 3x9, 3x11):
    2 3   5   7        11    13          17    19          23    25          29    31          35...
          ^
  4. Repeat step 3. indefinitely. On each repetition a new prime is identified (marked ^) and its multiples eliminated (5x5, 5x7) until all the primes in the starting list have been found:
    2 3   5   7        11    13          17    19          23                29    31            ...
              ^

When we have exceeded the square root of the upper limit of our range, we have the desired sequence of prime numbers. In the example given above that will be achieved when we identify the prime '7', to give our list of all primes less than 36.

Limitations

Theoretically, these "sieve" algorithms could run over unlimited (infinite) numbers. Obviously, in practice, they are not scalable as the computational power required for multiplying rapidly increasing values is a serious limitation for finding prime numbers above say 10 million. Consider also that a typical 32 bit computer has a native unsigned integer limit of 4294967295, which has a square root of 65536 (rounded up integer).

Burnt Jet Homepage

This page is best viewed in a web browser that fully supports style sheets (CSS2). You will be able to view the content of this page in your current browser but some aspects may not be optimally rendered.
Live Instance