Share via

Small Basic: Prime Sieve

  • Article

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:

' 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]=2, A[3]=3, A[4]=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]=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 K = (2 * J) To MAX_NUM Step J

   A[K] = ""

EndFor

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.

 

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!

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

Additional Resources