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 }