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[2] to A[100] with numbers 2 to 100; A[1] is left empty because 1 isn’t a prime (see column 1). We start by examining A[2]; because it isn’t empty, we wipe out all its multiples (see column 2). That is, we set A[4], A[6], A[8] … to an empty string, "". We then examine A[3]; because it isn’t empty, we wipe out all its multiples (A[6], A[9], A[12], … ) . See column 3. We then examine A[4]; because it’s empty, we move on to A[5]. Because A[5] isn’t empty, we wipe out all its multiples (A[10], A[15], A[20], … ). See column 4. We continue in this way until we examine the last entry at A[100]. With this plan in mind, our implementation is shown in the Listing below.

Listing:

We start by setting A[2]=2, A[3]=3, …, A[100]=100 in a For loop (lines 6-8). We then start a loop to examine the elements of A in sequence, starring with A[2] (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 example, if we currently examining A[2] (that is, J=2), the loop counter K will take on the values: 4, 6, 8, …, 100. Similarly, if we are examining A[3] (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[2] through A[100]. If it finds a nonempty element, its prints it followed by a comma.

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!

Head to the Small Basic forum to get the most answers to your questions: 

http://social.msdn.microsoft.com/Forums/en-US/smallbasic/threads/   

And go to http://blogs.msdn.com/SmallBasic to download Small Basic and learn all about it!

Credits

This article was originally written by Majed Marji and Ed Price for the blog post, Small Basic: Prime Sieve, on the User Ed MSDN blog.

See Also

• Wiki: Small Basic Portal  
• Small Basic: How to Create For Loops
• Small Basic Getting Started Guide: Chapter 5: Loops
• Small Basic Curriculum: Lesson 1.4: Conditions and Loops

Additional Resources

• Prime Number Sieve