# 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