Prime Numbers in PowerShell

Dylan was using a number square to calculate prime numbers so it amused me to code up a couple of algorithms to show just how quick the sieve method actually is. I’ve done these in PowerShell because … reasons.

So as a baseline, here’s a basic way to calculate a prime. Start with a number and try to divide it by every number starting from 2 up to the square root of the number. I’ve used throw in a try/catch block to move to the next iteration of the outer loop without executing the Write-Host line.

for ($n = 3; $n -lt 100000; $n++) {
    try {
        for ($d = 2; $d -le [Math]::Sqrt($n); $d++) {
            if ($n % $d -eq 0) {
                throw
            }
        }
        Write-Host -NoNewLine "$n "
    }
    catch { }
}

Interestingly, all those exceptions add quite an overhead because this same algorithm using a local variable ran three times quicker on my machine (27 seconds for the first and 9 seconds for this)

for ($n = 3; $n -lt 100000; $n++) {
    $prime = $true
    for ($d = 2; $d -le [Math]::Sqrt($n); $d++) {
        if ($n % $d -eq 0) {
            $prime = $false
            break;
        }
    }
    if ($prime) {
        Write-Host -NoNewLine "$n "
    }
}

Obviously we should optimise this by removing even numbers as below and this, as you’d expect, halves the run time.

for ($n = 3; $n -lt 100000; $n += 2) {
    $prime = $true
    for ($d = 3; $d -le [Math]::Sqrt($n); $d += 2) {
        if ($n % $d -eq 0) {
            $prime = $false
            break;
        }
    }
    if ($prime) {
    }
}

Anyway, the sieve is all done in 0.75 seconds:

$ints = 0..100000
for ($i = 2; $i -lt [Math]::Sqrt($ints.length); $i++) {
    if ($ints[$i] -eq 0) {
        continue
    }
    for ($j = $i * $i; $j -lt $ints.length; $j += $i) {
        $ints[$j] = 0
    }
}
$ints | foreach { if ($_) { Write-Host -NoNewLine "$_ " } }

As the maximum number increases the differences become even more stark. At 1,000,000 the sieve completed in 11 seconds but the simple method took 129 seconds

For my timings, I used measure-command and removed the Write-Host lines.

Categories