Scripting Games, Advanced Event 6, Prime Time

When I first saw this one on the list I grinned a bit because one of the first real scripts I wrote in PowerShell was a translation of a procedure to calculate prime factors. I say "real" script here in the sense of "More than a couple of lines long" rather than "Of use in a real world situation"!

But this was actually a different problem – in fact just a simple prime sieve.

Here it is:

  1 param ([int]$max=200)	# Find primes up to $max
  2 
  3 $sieve=,1*($max+1)	# Initialise sieve, assume all primes to start
  4 
  5 for ($i=2; $i -le $max; $i++) {
  6 	# Find next prime entry in sieve
  7 	if ($sieve[$i]) {
  8 		$i
  9 		# Blank out higher multiples of current prime in sieve
 10 		for ($j=$i*$i; $j -le $max; $j+=$i) {$sieve[$j]=0}
 11 	}
 12 }

The "sieve" in a prime sieve algorithm is just a list of numbers that are either possible primes, or which have been shown to have factors.  A couple of things I like about PowerShell (among many things!): initialising an array of number from 1 to 12 (or whatever) is just $a=1..12; Initialising an array of a single item and giving it a value of one is: $a=,1; But if you apply the multiplication operator to an array PowerShell will duplicate the array by the number of times specified.  To create a 200 element array of integers with all array entries set to 1, use: $a=,1*200.  Nice!  This is used at line 3 to create the sieve.  The "1" in this case is just a boolean value to indicate that the number at array position [x] is a prime.

{Note: I could’ve used $true and $false rather than 0 and 1 in the sieve, but old habits die hard, sorry!}

We then start at 2 and count up to $max looking for the next prime – in other words, where sieve[i] is true (line 7).  Initially the whole sieve is indicating that every number is a prime (because no factors have been found yet), so $sieve[2] is true.

Every time a match is found, the script displays the match (line 8) and then does the sieving thing.  Multiples of the current prime (in the first case 2, 4, 6, 8, …..) are marked in the sieve by looping up to $max, in increments of the current prime, setting the corresponding sieve elements to false (0) along the way (line 10).  There’s a small optimisation here; elements in the sieve less than the square of the current prime can be skipped because they have already been set by previous factors – so we start setting entries at ($i*$i).

/\/\o\/\/ mentioned performance in his post; I don’t think it was me on the #powershell IRC channel (I can’t find a good IRC client – can anyone recommend one??)  But here’s a sample run on the first 100,000 primes (faster than a brute-force attack to 200!):

PS > (Measure-Command {./primes.ps1 100000}).tostring()
00:00:02.7081285
PS >

And on a cool million:-)

PS > (Measure-Command {./primes.ps1 1000000}).tostring()
00:01:01.5248231
PS >

So, this was about prime numbers – I’ll post my prime factor script (a translation from Rexx, S/370 Assembler, C and Basic in reverse chronological order:-) in a future blog post.

Advertisements

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