2008 Winter Scripting Games
Thomas Lee's Solution to Advanced Windows PowerShell Event 6: Prime Time
About the Author Thomas Lee is Chief Architect for the EMEA Group of the Global Knowledge companies. Thomas is well-known through the IT world as a trainer, presenter, and columnist for Server Management and PC Pro magazines. Thomas is a Microsoft MVP, and has co-authored a number of books on computer technology. |
Prime Time
It was exciting getting an invitation from the Scripting Guys to take part in the latest Scripting Games. I’m incredibly busy, but the chance to take part was just too good to pass up, so I accepted the challenge. A few weeks after the initial mail, as promised, I got my assignment: write a script to calculate all the prime numbers between 1 and 200. A reference to an algorithm was given and the work began.
The script is really pretty easy, and is based on the Sieve of Eratosthenes. If you look at the script:
| • | We start the real script by declaring two variables. $Highest is the highest number we want to calculate, while $Potential is an array of potential primes. The idea of the algorithm is to iterate over this array, knocking out all multiple of a prime as we go. |
| • | In the main loop we vary the loop counter $i from 2 to the highest number. I start at 2 since 1 is not really a prime number! |
| • | For each iteration, we look at the array member and, if it’s not -1, it’s a prime. |
| • | Once we find a prime, we then look forward in the array, and knock out any multiples of this just-found prime (by setting the array value to -1). |
| • | When we’re all done, we review the array and print out the primes (the array members that are not set to -1). |
This was a pretty simple task, and it took me around 30 minutes to research and write. A couple of points:
| • | Array indices in PowerShell start at 0 which threw me for a minute, till I decided to just create $potential from 0..$highest. That way $i and $potential[$i] were the same number. |
| • | This is not a good use of PowerShell in terms of system administration scripting. It is a good demonstration that PowerShell can perform some basic computing. [Ed: Whine, whine, whine...] |
| • | Debugging loops like this is where a great debugger would come in handy. If only Mirosoft could integrate PowerShell into Visual Studio?!?!? |
| • | I’ve added more comments here to clarify the code, and I’ve not tried any 1-liner type optimization. The idea was to keep it simple! |
Here’s the script:
# primes.ps1
# script to calculate prime numbers from 1 to 200
# thomas lee - tfl@psp.co.uk
# Algorithm based on Sieve of Eratosthenes
# See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for detaqils
# 1. Define parameters
$highest = 200 # highest prime
# Create an array of potential primes
$potential = 0..$highest
# 2. Loop through potential primes
for ($i=2; $i -le $highest; $i++) {
$prime = $potential[$i]
# 3. if not already knocked out, this number must be prime
If ($prime -ne -1) {
# 4. So since this is a prime, knock out the multiples or $Prime
for ($j=$i+$prime; $j -le $highest; $j+=$prime) {
$potential[$j]=-1
} #end for $j
} #end if
}#end for $i
# 5. Finally, print results
"Primes from 2 to 200 are:"
for ($i=2; $i -lt $highest; $i++){
if ($potential[$i] -ne -1) {$i}
}
