Code Pyre

All Code Dies and Burns in Time

Fork me on GitHub

Project Euler: Problem 7 in Parasitic PowerShell

| Comments

This post leverages my OSS project Prototype.ps to support parasitic object creation. If you haven’t read the introduction posts Part 1 and Part 2, I would recommend reading them as I build off of their functionality and theory. If you don’t care how it works, read on my friend.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10,001st prime number?

Solving Using a Prototypal Object
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
function New-PrimeGenerator {
  $prototype = New-Prototype
  $prototype | Update-TypeName
  $prototype | Add-Property Primes @(2,3,5)
  $prototype | Add-Property Cache @{2=$true; 3=$true; 4=$false; 5=$true}
  $prototype | Add-Property Bound 5
  $prototype | Add-Property BoundIncrement 1000
  $prototype | Add-Property LastExpansionPrimeCount 3
  $prototype | Add-ScriptProperty MaxPrime {$this.Primes | select -last 1}
  $prototype | Add-Function IsPrime {
    param($value)
    while ($this.MaxPrime -lt $value) { $this.Expand() }
    return $this.Cache[$value] -ne $null
  }
  $prototype | Add-Function FindNthPrime {
    param($value)
    while ($this.Primes.Length -lt $value) { $this.Expand() }
    return $this.Primes[$value-1]
  }
  $prototype | Add-Function RoundToNextMultiple {
    param($base, $multiple)
    $remainder = $base % $multiple;
    if($remainder -eq 0) { $base }
    else { $base + $multiple - $remainder }
  }
  $prototype | Add-Function Expand {
    $oldBound = $this.Bound
    if($this.LastExpansionPrimeCount -le $this.Primes.Length) {
      $this.Bound += $this.BoundIncrement
    }
    $limit = $this.Bound
    $cache = $this.Cache
    $this.Primes | % {
      for ($i=$this.RoundToNextMultiple($oldBound,$_); $i -le $limit; $i += $_ ) {
        if(!$cache.ContainsKey($i)) { $cache[$i] = $false }
      }
    }
    ($oldBound+1)..$limit | ? { $cache[$_] -eq $null } | % {
      $cache[$_] = $true
      $this.Primes += @($_)
      for ($i=$this.RoundToNextMultiple($oldBound,$_); $i -le $limit; $i += $_ ) {
        if(!$cache.ContainsKey($i)) { $cache[$i] = $false }
      }
    }
    $this.LastExpansionPrimeCount = $this.Primes.Length
  }
  $prototype
}

function Solve-Problem7 {
  $generator = New-PrimeGenerator
  Write-Host "Elapsed Time (s): " (Measure-Command {$generator.FindNthPrime(10001)}).TotalSeconds
  Write-Host "Elapsed Time (s): " (Measure-Command {$generator.FindNthPrime(10001)}).TotalSeconds
  Write-Host "Solution: " ($generator.FindNthPrime(10001))
}

Solve-Problem7

Elapsed Time (s):  33.1381042
Elapsed Time (s):   0.0003987
Solution:  104743

Comments