Small Basic: Prime Sieve


Prime Sieve

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)    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.

primesieve1
Figure 1: Illustrating the Sieve of Eratosthenes method of finding prime numbers

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.

primesieve2c

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:

 1 ' PrimeSieve.sb

 2 ' Finds all prime numbers below a certain number

 3

 4 MAX_NUM = 100         ' to find all primes <= 100

 5

 6 For N = 2 To MAX_NUM  ' Fill array A

 7   A[N] = N            ' A[2]=2, A[3]=3, A[4]=4 ...

 8 EndFor

 9

10 For J = 2 To MAX_NUM  ' Examine each number in turn

11   If (A[J] <> "") Then   ' If the number isn’t crossed-out

12     FOR K = (2 * J) To MAX_NUM Step J ' cross its multiples

13       A[K] = ""

14     EndFor

15   EndIf

16 EndFor

17

18 ' The remaining non-empty elements are primes. Print them

19 For N = 2 To MAX_NUM

20   If (A[N] <> "") Then

21     TextWindow.Write( A[N] + ", ")

22   EndIf

23 EndFor

24 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).

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!

Small and Basically yours

- Ninja Ed & Majed Marji

Comments (4)

  1. Glenn Westmore says:

    Some interesting facts and puzzles about Prime Numbers and Magic Squares, Smith Numbers, and Arithmetic and Palindromic Primes on this blog: http://www.glennwestmore.com.au.

  2. Thanks for sharing, Glenn!

  3. Thank you, Ed and Majed for your post. Can you recover images in this post? I can't see them.
    By the way, I wrote a graphical version of prime sieve program PKV420.

Skip to main content