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.
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.
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:
https://social.msdn.microsoft.com/Forums/en-US/smallbasic/threads/
And go to https://blogs.msdn.com/SmallBasic to download Small Basic and learn all about it!
Small and Basically yours
- Ninja Ed & Majed Marji