# Prime Sieve Overview

Prime numbers have fascinated people since ancient times. The Sieve of Eratosthenes provides one way to find all the prime numbers less than a given number. The procedure, which is illustrated in Figure 1, works as follows:

1. Cross out number 1 because 1 isn’t a prime number.
2. Circle number 2 because 2 is prime.
3. 3)    Cross out all multiples of 2 (i.e., 4, 6, 8 …) because they aren’t primes.
4. The next non-crossed number after 2 is 3. This number is thus a prime and we circle it.
5. Cross out all multiples of 3 (i.e., 6, 9, 12 …) because they aren’t primes.
6. The next non-crossed number after 3 is 5. This number is thus a prime and we circle it.
7.  Cross out all multiples of 5 because they aren’t primes.
8. Continue is this manner. The circled numbers at the end are prime numbers. Figure 1: Illustrating the Sieve of Eratosthenes method of finding prime numbers

# Sample Application

In this example, we’ll develop an application that demonstrates this procedure by finding all prime numbers below 100. Our plan for developing this program is illustrated in Figure 2. Figure 2: Illustrating the plan for writing the Sieve of Eratosthenes program

We’ll start by initializing A to A with numbers 2 to 100; A is left empty because 1 isn’t a prime (see column 1). We start by examining A; because it isn’t empty, we wipe out all its multiples (see column 2). That is, we set A, A, A … to an empty string, "". We then examine A; because it isn’t empty, we wipe out all its multiples (A, A, A, … ) . See column 3. We then examine A; because it’s empty, we move on to A. Because A isn’t empty, we wipe out all its multiples (A, A, A, … ). See column 4. We continue in this way until we examine the last entry at A. With this plan in mind, our implementation is shown in the Listing below.

Listing:

`' PrimeSieve.sb`
`' Finds all prime numbers below a certain number`
```MAX_NUM = 100         ````' to find all primes <= 100`
`For` `N = 2 ``To` `MAX_NUM  ``' Fill array A`
` ````A[N] = N            ````' A=2, A=3, A=4 ...`
```EndFor                 ```

`For` `J = 2 ``To` `MAX_NUM  ``' Examine each number in turn`
`  ``If` `(A[J] <> ``""````) ````Then`   ``` ' If the number isn’t crossed-out```
`    ````FOR K = (2 * J) ````To` ``` MAX_NUM ````Step` ``` J ````' cross its multiples`
`      ````A[K] = ````""`
`    ````EndFor   ```
`  ``EndIf`
` ``EndFor`

` ``' The remaining non-empty elements are primes. Print them`
`For` `N = 2 ``To` `MAX_NUM`
`If` `(A[N] <> ``""````) ````Then`
```TextWindow.Write( A[N] + ````", "``)`
`EndIf`
`EndFor`
`TextWindow.WriteLine(``""``)`

# Output

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,

We start by setting A=2, A=3, …, A=100 in a For loop (lines 6-8). We then start a loop to examine the elements of A in sequence, starring with A (line 10). If the examined element is empty, we move on to the next element. Otherwise (line 11), we start a loop to wipe out its multiples (lines 12-14). This loop is shown below for convenience.

For K = (2 * J) To MAX_NUM Step J

A[K] = ""

EndFor

For example, if we currently examining A (that is, J=2), the loop counter K will take on the values: 4, 6, 8, …, 100. Similarly, if we are examining A (that is, J=3), the loop counter K will take on the values: 3, 6, 9, …, 99, and so on. After processing all elements of A, the program makes another round through A to print the non-empty elements (lines 19-24). The For loop at line 19 just checks A through A. If it finds a nonempty element, its prints it followed by a comma.

# Try It Out!

The Write loop in the Listing (lines 19-24) is redundant. You can display the prime numbers immediately after finding them, which can be done inside the first For loop (lines 10-16). Modify the program to eliminate the Write loop (lines 19-23).

# Now What?

Do you have any questions? Ask us! We're full of answers and other fine things!