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.

Here’s my answer

   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.

Advertisements

One Response to “Scripting Games Event 6 Select-Prime”

  1. Jason Archer Says:

    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.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: