Scripting Games Event 6 Select-Prime

26. February 2008 Andy Schneider Comments (4)

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.

Tags:

Comments (4) -

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

Vedic Math 1/14/2009 3:01:35 PM

Hey Jason, your suggestion is brilliant! Smile

Matthew Painter 8/21/2010 1:08:29 AM

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}
      $_
   }

Matthew Painter 8/21/2010 2:08:32 AM

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
   ""

Comments are closed