## Scripting Games Event 6 Select-Prime

Event six was a classic programming math problem. Find all the prime numbers in a given range. For this particular problem, the range was between 1 and 200.

`   1: filter select-prime `
`   2: { `
`   3:     if (\$_ -eq 1) {return \$null}`
`   4:     for (\$i=2;\$i -le ([int][Math]::Sqrt(\$_));\$i++) `
`   5:         { `
`   6:         if (\$_ % \$i -eq 0 ) {return}`
`   7:         }`
`   8:     \$_`
`   9: } `
`  10: 1..200 | select-prime`

It turns out that in order to find if a prime number we can use the modulus operator. This math operator simply returns the remainder when one number is divided by another

If a number n % x  = 0 where x is not 1 or n, then the number will not be prime.

`   1: PS U:> 6 % 2`
`   2: 0`
`   3: PS U:> 5 % 3`
`   4: 2`
`   5: PS U:> 5 % 2.5`
`   6: 0`
`   7: PS U:> 9 % 2`
`   8: 1`
`   9: PS U:> 9 % 3`
`  10: 0`

So this will work if we just went from 2 to N. But it turns out that is way more work than necessary. We only need to go up to the Square Root of N and we can call it prime.

I really thought I was being super cool and iterated up the square root of the number. Turns out the calls into .NET to calculate the square root were to costly to make my efficiency efficient.

`   1: PS C:usersandysDesktop> cat C:usersandysDesktopprimes.ps1`
`   2: filter select-primeQuickly`
`   3: {`
`   4:         if (\$_ -eq 1) {return \$null}`
`   5:         for (\$i=2;\$i -le ([int][Math]::Sqrt(\$_));\$i++)`
`   6:                 {`
`   7:                 if (\$_ % \$i -eq 0 ) {return}`
`   8:                 }`
`   9:         \$_`
`  10: }`
`  11:  `
`  12: filter select-primeSlowly`
`  13: {`
`  14:         if (\$_ -eq 1) {return \$null}`
`  15:         for (\$i=2;\$i -le \$_;\$i++)`
`  16:                 {`
`  17:                 if (\$_ % \$i -eq 0 ) {return}`
`  18:                 }`
`  19:         \$_`
`  20: }`
`  21:  `
`  22: "Quickly"`
`  23: ""`
`  24: measure-command {1..200 | select-primeQuickly}`
`  25: "Slowly"`
`  26: ""`
`  27: measure-command {1..200 | select-primeSlowly}`
`  28: PS C:usersandysDesktop> C:usersandysDesktopprimes.ps1`
`  29: Quickly`
`  30:  `
`  31: Days              : 0`
`  32: Hours             : 0`
`  33: Minutes           : 0`
`  34: Seconds           : 0`
`  35: Milliseconds      : 734`
`  36: Ticks             : 7346876`
`  37: TotalDays         : 8.5033287037037E-06`
`  38: TotalHours        : 0.000204079888888889`
`  39: TotalMinutes      : 0.0122447933333333`
`  40: TotalSeconds      : 0.7346876`
`  41: TotalMilliseconds : 734.6876`
`  42:  `
`  43: Slowly`
`  44:  `
`  45: Days              : 0`
`  46: Hours             : 0`
`  47: Minutes           : 0`
`  48: Seconds           : 0`
`  49: Milliseconds      : 346`
`  50: Ticks             : 3469459`
`  51: TotalDays         : 4.0155775462963E-06`
`  52: TotalHours        : 9.63738611111111E-05`
`  53: TotalMinutes      : 0.00578243166666667`
`  54: TotalSeconds      : 0.3469459`
`  55: TotalMilliseconds : 346.9459`

Looking at the results, what I thought was going to be quick was actually a lot slower! The version that calls into .NET ran in 736 milliseconds and the version that did not ran in 346 milliseconds.

Goes to show that when you are programming or scripting, what we think may be a gain in efficiency, may very well not be, as I learned in this exercise. Jason Archer 3/20/2008 9:03:22 AM

The script could be improved.  Since ([int][Math]::Sqrt(\$_)) will never change per execution of the filter, you don't need to call it for every iteration of the loop.  This is faster than either of the above filters:

filter select-prime
{
if (\$_ -eq 1) {return \$null}
\$sqrt = [int][Math]::Sqrt(\$_)
for (\$i=2;\$i -le \$sqrt;\$i++)
{
if (\$_ % \$i -eq 0 ) {return}
}
\$_
}

(Also, since these filters run so fast you should do your tests with multiple iterations.  Like 100 or so.) Hey Jason, your suggestion is brilliant!  Love this stuff

Here is an even quicker filter for the range 1-200 (once you start testing larger numbers it bogs down.

filter select-primeREGEX
{
\$primeUN = "1" * \$_
if(\$primeUN -match "^1?\$|^(11+?)\1+\$") {return}
\$_
} For a range of numbers 1-300 the regex version is quickest and after that Andy's quick version is the quickest.

filter select-primeQuickly
{
if (\$_ -eq 1) {return \$null}
for (\$i=2;\$i -le ([int][Math]::Sqrt(\$_));\$i++)
{
if (\$_ % \$i -eq 0 ) {return}
}
\$_
}

filter select-prime-JasonArcher
{
if (\$_ -eq 1) {return \$null}
\$sqrt = [int][Math]::Sqrt(\$_)
for (\$i=2;\$i -le \$sqrt;\$i++)
{
if (\$_ % \$i -eq 0 ) {return}
}
\$_
}

filter select-primeSlowly
{
if (\$_ -eq 1) {return \$null}
for (\$i=2;\$i -le \$_;\$i++)
{
if (\$_ % \$i -eq 0 ) {return}
}
\$_
}

filter select-primeREGEX
{
\$primeUN = "1" * \$_
if(\$primeUN -match "^1?\$|^(11+?)\1+\$") {return}
\$_
}

"Quickly"
(measure-command {1..300 | select-primeQuickly}).TotalMilliseconds
""
"Slowly"
(measure-command {1..300 | select-primeSlowly}).TotalMilliseconds
""
"Regex"
(measure-command {1..300 | select-primeREGEX}).TotalMilliseconds
""
"JasonArcher"
(measure-command {1..300 | select-prime-JasonArcher}).TotalMilliseconds
""