2008 Winter Scripting Games

Solution to Advanced Windows PowerShell Event 6: Prime Time

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

Solutions are also available for VBScript and Perl.

Prime Time

Event 6 turned out to be a little easier than anticipated, at least for the Scripting Guys. When we first read up on the Sieve of Eratosthenes we thought, “Good heavens, no one will ever be able to solve this event!” As it turned out, however, the problem was that the explanation of the Sieve of Eratosthenes was needlessly complicated; the underlying concept was actually fairly easy to understand, and even easier to mimic in Windows PowerShell. How easy? This easy:

$arrNumbers = @()

for ($i = 1; $i -le 200; $i++) 
    {$arrNumbers += $i}

$arrNumbers[0] = "Not prime"
$strPrimeNumbers = "2`n"

$intDivisor = 2

do 
    {
        for ($j = 0; $j -le $arrNumbers.length - 1; $j++)
            { 
                if ($arrNumbers[$j] -ne "Not prime")
                    { 
                        $intResult = $arrNumbers[$j] % $intDivisor
                        if ($intResult -eq 0)
                            {$arrNumbers[$j] = "Not prime"}
                    }
             }

         for ($i = 2; $i -le $arrNumbers.length; $i++)
            {
               if ($arrNumbers[$i] -ne "Not prime")
                  {
                       $intDivisor = $arrNumbers[$i]
                       $strPrimeNumbers = $strPrimeNumbers + $intDivisor + "`n"
                       break
                   }
              }
    }
until ($intDivisor -ge $arrNumbers.length - 1)

$strPrimeNumbers

As you can see, the script we came up with to solve Event 6 is one of the shorter scripts in the Advanced Division; at the same time, it’s also one of the more-confusing scripts, at least at first glance. With that in mind, let’s see what we can do to clear up some of the confusion.

Things actually start off simple enough; in line 1 we use this bit of code to create an empty array named $arrNumbers:

$arrNumbers = @()

As soon as we have our empty array in hand we then use a for loop to add the numbers 1 through 200 to this array:

for ($i = 1; $i -le 200; $i++) 
    {$arrNumbers += $i}

We’re going to use this array to keep track of which numbers are prime numbers and which ones aren’t. By definition, the number 1 is not a prime number; hence we set the value of array item 0 to the string Not prime:

$arrNumbers[0] = "Not prime"

Also by definition, the number 2 is a prime number. Hence we add the number 2 and a carriage return-linefeed to a string value named $strPrimeNumbers:

$strPrimeNumbers = "2`n"

Our next step is to assign the value 2 to a variable named $intDivisor. Why? Well, we decided to tackle this problem using the Sieve of Eratosthenes. This algorithm starts with the premise that 1 is not a prime number but that 2 is. From there the Sieve takes the number 2 and divides it into all the other numbers in our collection. If 2 divides evenly into a number then we know that this number is not prime (prime numbers can only be evenly divided by 1 and themselves). In turn, we remove this number from the list of potential prime numbers, something we do by marking the value as Not prime in our array.

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

Well, maybe but, then again, maybe not. That’s why, instead of stopping after we divide 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.

Confusing? Hey, don’t blame us; blame Eratosthenes!

Anyway, that’s why we set $intDivisor to 2: to find all the prime numbers between 1 and 100 we have to first try to divide all those values by 2.

To do that, we set up a do loop designed to run until $intDivisor is greater than or equal to the Length of our array minus 1:

until ($intDivisor -ge $arrNumbers.length - 1)

How did we come up with that crazy criteria? Well, we have 200 items in our array; that means that the length is equal to 200. That also means that the largest index number in the array is 199. (The largest index number, or upper bound, is always one less than the total number of items in the array.) Thus we want to continue looping until our divisor hits 200; when that happens, there are no more items left in the array.

Inside the loop, we set up a for loop that runs through all the items in the array (items 0 through 199):

for ($j = 0; $j -le $arrNumbers.length - 1; $j++)

For each item in the array we start by checking to see if the value of that item is the string Not prime:

if ($arrNumbers[$j] -ne "Not prime")

If the value is equal to Not prime that means we’ve already determined that this is not a prime number; consequently, we skip that item, go back to the top of the loop, and try the next number. If the item is not equal to Not prime we execute the following block of code:

$intResult = $arrNumbers[$j] % $intDivisor
if ($intResult -eq 0)
    {$arrNumbers[$j] = "Not prime"}

In the first line we used the modulus operator (%) to divide $intDivisor into array item $j. The modulus operator is designed to divide two numbers and then return only the remainder. If the remainder is equal to 0 (line 2) that means that the number can be evenly divided by $intDivisor. And because that also means that the number is not a prime number, we use line 3 in the code block to change the value of the array item to Not prime.

And then we repeat the process with the next array item.

That takes care of dividing all the numbers in the array by 2. Now we need to divide all those numbers by the next prime number. How do we know which is the next prime number? Well, that’s what our next for loop is for. Here we loop through the entire array, looking for the first item that is not equal to the string Not prime (in other words, the first item that’s still a number). What do we do when we find this value? Three things:

$intDivisor = $arrNumbers[$i]
$strPrimeNumbers = $strPrimeNumbers + $intDivisor + "`n"
break

In line 1, we’re assigning the value of this number to $intDivisor. That means that, the next time through our do loop, we’ll divide all the numbers in the array by 3. In line 2, we add this number and a carriage return-linefeed to the string $strPrimeNumbers; that’s because we know that this value is a prime number. Finally, we use the break command to break out of the for loop and return to the do loop.

Whew!

The rest is easy; in fact, once our do loop ends all we have to do is echo back the value of $strPrimeNumbers and we’ll have our list of prime numbers. If all goes well, that list should look like this:

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

And guess what? In a Scripting Guys first, and as near as we can tell, everything did go well.

Top of page