This continues my series of solution posts for the 2008 Scripting Games with my solution for the Advanced Event 6. This was an interesting challenge because it’s a basic algorithms test … Mow, the scripting guy came up with some interesting brute-force solutions … but nearly everyone else just implemented the Sieve of Eratosthenes, since it’s the easiest of the prime sieves to understand.

I was slightly annoyed to be porting this simple algorithm to PowerShell, but I didn’t have the time to use an improved sieve, so I just ported it as directly as I could, without optimizing it for the PowerShell syntax, or removing any steps:


param($max = 200)                   # We will find all primes less than this number
$sieve = new-object bool[] ($max+1) # By sorting this sieve as Eratosthenes would
$n = 2                              # We know that 2 is the first prime
$p = $n*$n                          # Lowest possible unmarked non-prime is it's square
while($p -lt $max){                 # Test up to the sqrt of $max
  do{                               
    $sieve[$p] = $true              # mark it as not a prime
    $p += $n                        # if it's a multiple of a prime
  } while($p -le $max)              # all the way up to MAX
  do{++$n}while($sieve[$n])         # the next unmarked number is prime
  $p = $n*$n                        # the lowest possible unmarked non-prime is it's square
}                                   # all NON-PRIME numbers were flagged
for($p=2;$p -le $max;++$p){
   if(!$sieve[$p]) { $p }           # so we print out the ones that weren't
}
 

Mow asked about performance (because he wrote a brute -force solution, since the challenge was only to find up to 200) ... and I was reluctant to even mention it, because my script is such a direct port of the generalized algorithm that it’s guaranteed not to perform well, but I thought I’d post these numbers because they show how good Chris’s solution is. Remember these are numbers from my deliberately underpowered machine at work — don’t compare them to numbers from other computers — if you want to know how these scripts compare to yours, copy the code and run them all on your PC.


[82]: gph 6

Duration Lines Words Chars Type   Commmand
-------- ----- ----- ----- ----   --------
 0.01300    10    54   311 Script $n = C:\Scripts\Chris6.ps1 200
 0.11000    10    54   311 Script $n = C:\Scripts\Chris6.ps1 2000
 1.23200    10    54   311 Script $n = C:\Scripts\Chris6.ps1 20000
 0.25800    15   138   938 Script $n = C:\Scripts\Event6.ps1 200
 0.61500    15   138   938 Script $n = C:\Scripts\Event6.ps1 2000
 7.01600    15   138   938 Script $n = C:\Scripts\Event6.ps1 20000
 

Oh, and by the way, that output is from a Get-PerformanceHistory script…

Postscript

The guys in #PowerShell on IRC were making fun, and claiming that my problem was the initialization of the bool array (it’s not), so I had to explain the performance difference … and it’s really quite simple. Chris used $p = $n*$n to calculate the square of the iterator, which is a lot faster than $p = [Math]::Pow($n,2) which is what I used originally. I changed the script above to use $n*$n because that’s clearly a better choice for calculating squares … I wouldn’t want people using [Math]::Pow after seeing that difference. Here’s the new speed report (and yes, I made a new version of Get-PerformanceHistory which calculates averages if your command starts with a range like 1..10):


[95]: gph 2

Duration   Average Lines Words Chars Type   Commmand
--------   ------- ----- ----- ----- ----   --------
1:24.17800 8.41780    10    54   311 Script 1..10 | % { $a = .\Chris6.ps1 100000 }
1:08.36800 6.83680    15   137   948 Script 1..10 | % { $b = .\Event6.ps1 100000 }
 

In the interests of full disclosure … (and because I’m and algorithms optimization geek, in case you haven’t noticed) that loop on the end of my script that outputs the values … and the fact that I therefore break out of the calculation loop when I hit the square root of the $max value … makes my script slightly faster for huge values of max (as above) , and somewhat slower for small values:


Duration Average Lines Words Chars Type   Commmand
-------- ------- ----- ----- ----- ----   --------
34.40500 3.44050    15   138   988 Script 1..10 |  % { $b = .\Event6UsingPow.ps1 10000 }
 6.44300 0.64430    15   137   948 Script 1..10 |  % { $b = .\Event6.ps1 10000 }
 5.86300 0.58630    10    54   311 Script 1..10 |  % { $b = .\Chris6.ps1 10000 }