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