26. February 2008
Andy Schneider
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.