Add to Technorati Favorites
Welcome to ThePowerShellGuy.com Sign in | Join | Help

Scripting Games 2008 Advanced Windows PowerShell Event 6

My solution to Advanced event 6

2;2..200 |? {$i=$_;(2..($i -1) |% {$i%$_}) -notcontains 0}

Warning, I really went Brute Force here, this is probably the most ineffective way to do this :

PoSH> 2;2..200 |? {$i=$_;(2..($i -1) |% {$i%$_}) -notcontains 0}                                                        
2                                                                                                                       
3                                                                                                                       
5                                                                                                                       
7                                                                                                                       
11                                                                                                                      
13                                                                                                                      
17                                                                                                                      
19                                                                                                                      
23                                                                                                                      
29                                                                                                                      
31                                                                                                                      
37                                                                                                                      
41                                                                                                                      
43                                                                                                                      
47                                                                                                                      
53                                                                                                                      
59                                                                                                                      
61                                                                                                                      
67                                                                                                                      
71                                                                                                                      
73                                                                                                                      
79                                                                                                                      
83                                                                                                                      
89                                                                                                                      
97                                                                                                                      
101                                                                                                                     
103                                                                                                                     
107                                                                                                                     
109                                                                                                                     
113                                                                                                                     
127                                                                                                                     
131                                                                                                                     
137                                                                                                                     
139                                                                                                                     
149                                                                                                                     
151                                                                                                                     
157                                                                                                                     
163                                                                                                                     
167                                                                                                                     
173                                                                                                                     
179                                                                                                                     
181                                                                                                                     
191                                                                                                                     
193                                                                                                                     
197                                                                                                                     
199                                                                                                                     
PoSH> (measure-command {2;2..200 |? {$i=$_;(2..($i -1) |% {$i%$_}) -notcontains 0}}).tostring()                         
00:00:02.9077541                                                                                                        
PoSH>

As you can see this took almost 3 seconds, this solution is very slow because I check EVERY modulus possible for every number.

This is a nice event to compare performance, as 3 seconds might not look that bad try performance for bigger numbers, here is mine for the primes until 5000 :

(measure-command {./event6.ps1}).tostring()

00:56:02.3067842

I'm sure most solutions will be much faster, I'm curious for Chris warwick 's solution I think he mentioned 10000 in a minute on the #powershell IRC Channel  , surly better as my almost an hour for 5000 ;-)

And to how other solutions compare, I'm sure Jaykul also will come with a fast solution

Enjoy,

Greetings /\/\o\/\/

Published Tuesday, February 26, 2008 3:37 PM by MoW

Comments

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

Primes to 10000

PS C:\scripts> (measure-command {.\test.ps1 10000}).tostring()

00:00:55.6328443

Tuesday, February 26, 2008 4:33 PM by Jason Clement

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

$p = 2..$args[0]

for ($i = 0; $i -lt $p.length-1; $i++)

{ $p = $p[0..$i] + ($p[($i+1)..($p.length-1)] | where {$_ % $p[$i] -ne 0}) }

$p

Interesting thing is that my perl solution runs in about a second.  In fact, everything seems to run much much faster in perl, which makes me regret that I've ignored it for all these years...

Tuesday, February 26, 2008 4:51 PM by Jason Clement

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

No complaints...

(measure-command .\a6.ps1 10000}).tostring()

00:02:31.7889512

Well done for getting it under a minute.  I used the Sieve approach but I'm sure my code is inefficient (obviously... 2.5 minutes..).  I used math::divrem for the event but afterwards found that % works just fine (hey, who knew..).  That change cut 1.5 mins out of 10000.

I'm pretty new to ps, still learning here (and as simple as the events in the competition are, they're great practice to learn by).  I'd love to get feedback if anybody has any.

param([int]$rangemax=10000)

$rangeMin = 2

$shelf = [math]::Floor([math]::Sqrt($rangeMax))

$possibles = @($rangeMin..$rangeMax)

foreach( $c in 2..$shelf )

{

for( $i=0 ; $i -lt $possibles.Length  ; $i++ )

{

$rem = -1

if( ($possibles[$i] -lt 3 ) -or ( $c -eq $possibles[$i] ) ) { continue }

if( ($possibles[$i] % $c) -eq 0 ) { $possibles[$i] = -1} # -1 being used as a "not a prime" flag

}

}

$possibles |? { $_ -ne -1 }

Tuesday, February 26, 2008 5:10 PM by jturnage

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

Using an arraylist cuts it down to 12 seconds:

$p = [Collections.ArrayList](2..$args[0])

for ($i = 0; $i -lt $p.Count - 1; $i++)

{ for ($j = $p.Count - 1; $j -gt $i; $j--)

 { if ($p[$j] % $p[$i] -eq 0)

   { $p.RemoveAt($j) }

 }

}

$p

(Measure-Command{.\test.ps1 10000}).ToString()

00:00:12.2469425

Tuesday, February 26, 2008 5:31 PM by Jason Clement

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

I just tested mine, for all primes from 1 - 10000

(Measure-Command {.\Untitled.ps1}).ToString()

00:00:01.5689015

For 1-200

(Measure-Command {.\Untitled.ps1}).tostring()

00:00:00.0101405

This was done in a VM, on a linux desktop, so I'm not too sure how much performance was impacted.

$start = 1

$end = 10000

$limit = [math]::sqrt($end)

$sieve = 2,3

$count = 4

while ($count -le $limit) {

$flag = 0  

foreach ( $s in $sieve) {

if ( $flag -eq 0) {  

if ( $count % $s -eq 0 ) { $flag = 1 } }

}

if ($flag -lt 1){ $sieve += $count}

$count += 1

}

$prime = @()

if ( $start -le $limit ) {

foreach ($s in $sieve) {

if ( ($s -gt $start) -and ($s -le $end)) { $prime += $s }

}

}

$count = $start + 1

while ($count -lt $end) {

$flag = 0

foreach ( $s in $sieve) {

if ( $flag -eq 0) {

if ( $count % $s -eq 0 ) { $flag = 1 }

}

}

if ($flag -lt 1){ $prime += $count}

$count += 1

}

Write-Output $prime

Tuesday, February 26, 2008 5:33 PM by justin.stokes

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

Rearranging the loops a little more powershelly helped (00:01:53.6477933 for 10000)

param([int]$rangemax=1000)

$possibles = @(2..$rangeMax)

2..[math]::Floor([math]::Sqrt($rangeMax)) |% { $c=$_ ;

1..($possibles.Length-1) |%{

if( ($c -ne $possibles[$_]) -and (($possibles[$_] % $c) -eq 0) ) {

$possibles[$_] = -1} # -1 being used as a "not a prime" flag

}}

$possibles |? { $_ -ne -1 }

Tuesday, February 26, 2008 5:34 PM by jturnage

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

(*warning* self confessed programming duffer and maths idiot)

I used an arraylist too, but didn't get anything like 12 seconds for 10000 primes, but since having a torrid time with Event 8, I've learnt that I don't need to pre-populate an array prior to using it. That's the one thing that is so useful about the Games, I learn something new each event.

PS>(measure-command{.\event6.ps1}).ToString()

00:00:27.7914614

$a = New-Object System.Collections.ArrayList

$max=[math]::round([math]::sqrt(10000),0)

1..10000| %{$a.add($_)} | out-null

for($x=1;$x -le 99999;$x++) {if ($a[$x] -gt $max){break};$b=$a[0..$x];

0..$a.count | % {if ($a[$_] -gt $a[$x]){if ($a[$_] % $a[$x] -gt 0){$b+=,$a[$_]}}}

$a = $b

}    

"The prime numbers between 0-10000"

$b[1..$b.count]

Wednesday, February 27, 2008 8:50 AM by nicktf

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

Using the sqrt of max as the test limit takes it down to less than a second.

$p = [Collections.ArrayList](2..$args[0])

$L = [int][Math]::Sqrt($args[0])

for ($i = 0; $p[$i] -le $L; $i++)

{ for ($j = $p.Count - 1; $j -gt $i; $j--)

 { if ($p[$j] % $p[$i] -eq 0)

   { $p.RemoveAt($j) }

 }

}

$p

(Measure-Command { .\test.ps1 10000 }).ToString()

00:00:00.9583131

Wednesday, February 27, 2008 9:53 AM by Jason Clement

# re: Scripting Games 2008 Advanced Windows PowerShell Event 6

As many have said using the square root of max is the major speed boost (I also skipped the even numbers in populating my data set in the vbscript version but it ruins the elegance in perl/powershell).

So useing your lovely one liner it becomes:

2..200|?{$i=$_;(2..[math]::sqrt($i)|%{$i%$_})-notcontains0}

My own solution was less elegant (didn't help I had to try to shoe-horn it in grid-view and had some issues forcing things to be objects). So mine for reference was:

$p=@{}

foreach($n in 2..200)

{

 $q=""|Select no;

 $q.no=$n;

 $p[$n]+=$q

}

$t=1

While($t++-lt15)

{

 $n=$t*2

 While($n-le200)

 {

   $p.remove($n)

   $n+=$t

 }

}

$p.psbase.values|Sort no|ogv

Wednesday, February 27, 2008 11:02 AM by Antony Smoothey

# 2008 Scripting Games - Solution for Advanced Event 6

PingBack from http://HuddledMasses.org/2008-scripting-games-solution-for-advanced-event-6/

Thursday, February 28, 2008 11:49 AM by 2008 Scripting Games - Solution for Advanced Event 6

# Scripting Games: Advanced PowerShell - Event 6 « PowerShell ?? ???????????? ??????????????

PingBack from http://xaegr.wordpress.com/2008/03/06/scripting-games-advanced-powershell-event-6/

Thursday, March 06, 2008 1:23 AM by Scripting Games: Advanced PowerShell - Event 6 « PowerShell ?? ???????????? ??????????????
Anonymous comments are disabled