2008 Winter Scripting Games

Solution to Advanced VBScript Event 6: Prime Time

Windows PowerShell solution to Event 6 in the 2008 Winter Scripting Games.

Solutions are also available for Windows PowerShell and Perl.

Prime Time

This script was an interesting one to write, mainly because the Scripting Guys had no idea what we were doing: although we were vaguely aware of the Sieve of Eratosthenes we had absolutely no idea how that algorithm worked. And even after we read a thorough explanation of the Sieve of Eratosthenes we still had no idea how that algorithm worked. Somehow or another, though, we managed to convert the Sieve of Eratosthenes to VBScript, and come up with the following solution:

Dim arrNumbers(199)

For i = 1 to 200
   arrNumbers(i - 1) = i
Next

arrNumbers(0) = "Not prime"
strPrimeNumbers = "2" & vbCrLf

intDivisor = 2

Do While intDivisor < Ubound(arrNumbers)
    For j = 0 to Ubound(arrNumbers)
        If IsNumeric(arrNumbers(j)) Then
            intResult = arrNumbers(j) Mod intDivisor
            If intResult = 0 Then
                arrNumbers(j) = "Not prime"
            End If
        End If
    Next

    For i = 2 to UBound(arrNumbers)
        If IsNumeric(arrNumbers(i)) Then
            intDivisor = arrNumbers(i)
            strPrimeNumbers = strPrimeNumbers & arrNumbers(i) & vbCrLf
            arrNumbers(i) = "Not prime"
            Exit For
        End If
    Next
Loop
    
Wscript.Echo strPrimeNumbers

As we noted, our solution – as you can probably tell just by looking at it – is based on the Sieve of Eratosthenes. In case you’re wondering, Eratosthenes was a Greek mathematician, poet, athlete, geographer and astronomer. Besides devising a way to calculate prime numbers, Eratosthenes also developed a system of latitude and longitude, and calculated the circumference of the Earth and the distance from the Earth to the Sun.

Which, back then, was all in a day’s work for a mathematician, poet, athlete, geographer and astronomer.

The Sieve of Eratosthenes is basically a brute force approach to solving problems. (No doubt that’s why we Scripting Guys were attracted to it in the first place.) The Sieve starts off with the premise that 1 is not a prime number, but that 2 is a prime number. From there the Sieve takes the number 2 and divides it into all the other numbers in our collection. (In this case, that’s going to be 2 divided into 3, 2 divided into 4, 2 divided into 5, etc.) If 2 divides evenly into a number then we know that this number is not prime, and we remove it from the list of potential prime numbers.

Now, what if 2 doesn’t divide evenly into a number (for example, 2 does not divide evenly into 9). Does that mean that this other number is a prime number?

Well, maybe, but we can’t say that this yet. Instead, after dividing all the numbers by 2 we find the smallest number that could not be evenly divided by 2 (which happens to be 3). We tag 3 as a prime number, then divide all the remaining numbers by 3. This continues until we’ve divided all the numbers in our collection by all the prime numbers that precede it.

So does out script actually do that? Let’s see for ourselves.

The script itself starts out by dimensioning an array named arrNumbers, configuring the array so it can hold 200 values (the numbers 1 through 200). That’s what we do here:

Dim arrNumbers(199)

We then use this block of code to add the numbers 1 through 200 to the array:

For i = 1 to 200
   arrNumbers(i - 1) = i
Next

Next we cheat a tiny bit:

arrNumbers(0) = "Not prime"
strPrimeNumbers = "2" & vbCrLf

Why is this cheating? Well, we know that 1 is not a prime number; hence, in the first line of code, we assign the string value Not prime to the first item in our array. Next, we know that 2 is a prime number; therefore, in the second line of code we assign the value 2 (and a carriage return-linefeed) to a variable named strPrimeNumbers. As you might have guessed, each time we find a prime number we’re going to add that number to this variable.

After assigning the value 2 to a variable named intDivisor (because we’re going to start off dividing numbers by 2) we set up a Do While loop that runs as long as intDivisor is less than the highest number in our array:

Do While intDivisor < Ubound(arrNumbers)

The first thing we do inside this loop is execute the following For loop:

For j = 0 to Ubound(arrNumbers)
    If IsNumeric(arrNumbers(j)) Then
        intResult = arrNumbers(j) Mod intDivisor
        If intResult = 0 Then
            arrNumbers(j) = "Not prime"
        End If
    End If
Next

What are we doing here? Well, as you can see, we’re looping through all the values in the array arrNumbers. For each value we use the IsNumeric function and the following line of code to make sure that the value is a number:

If IsNumeric(arrNumbers(j)) Then

Assuming we have a number, we then use the following line of code to divide that number by intDivisor and return only the remainder (that’s what the Mod operator does):

intResult = arrNumbers(j) Mod intDivisor

If the remainder is 0, that means that intDivisor can be evenly divided into the number; needless to say, that also means that this is not a prime number. In that case, we use this line of code to change the value in the array to Not prime:

arrNumbers(j) = "Not prime"

Now, suppose the remainder is not 0. Does that mean that this is a prime number? Well, maybe, but we can’t say for sure until we’ve finished divided this number by every other number. Therefore we don’t do anything at all; we just leave the value as-is.

When we’re all done, the first few items in our array should look like this:

Not prime
2
3
Not prime
5
Not prime
7
Not prime

Now it’s time to make our next pass through the collection of numbers; this block of code gets us ready to do just that:

For i = 2 to UBound(arrNumbers)
    If IsNumeric(arrNumbers(i)) Then
        intDivisor = arrNumbers(i)
        strPrimeNumbers = strPrimeNumbers & arrNumbers(i) & vbCrLf
        arrNumbers(i) = "Prime"
        Exit For
    End If
Next

What we’re doing here is looping through the array, starting with the third item in the array. (We can skip items 0 and 1, which represent the values 1 and 2, because we’ve already determined whether or not they are prime numbers.) Following the Sieve of Eratosthenes, we check the third item in the array to see if it is a number. If it is, that means that we’ve found the next prime number in the collection. Therefore, we assign this value to intDivisor. In addition, we add the value to the list of prime numbers; that’s what this line of code is for:

strPrimeNumbers = strPrimeNumbers & arrNumbers(i) & vbCrLf

After that we assign the string value Prime to that spot in the array; that ensures that we’ll skip this value the next time we enter the loop. (We need to skip it because we’ve already used it as a divisor.) Finally, and because we only want the smallest number left in the array, we call the Exit For statement to exit the loop. That has the effect of taking us back to the top of our Do loop, where we repeat this process all over again, this time using the new value of intDivisor.

And once we finish with the Do loop we can echo back the list of prime numbers simply by echoing back the value of the variable strPrimeNumbers:

Wscript.Echo strPrimeNumbers

Here, for your viewing pleasure, are the prime numbers between 1 and 200:

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
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199

Top of page