Skip to content

Instantly share code, notes, and snippets.

@msm-fc
Last active July 25, 2018 20:24
Show Gist options
  • Save msm-fc/d2c1b02dbd3152f6d28d69a2de2d4fb3 to your computer and use it in GitHub Desktop.
Save msm-fc/d2c1b02dbd3152f6d28d69a2de2d4fb3 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
<#
Sieve of Eratosthenes in PowerShell
converted from C++ and Java code found here:
http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes
2018 Matt Musante
Public Domain
#>
function runEratosthenesSieve{param ([int]$upperBound)
[int]$upperBoundSquareRoot = [Math]::Floor([math]::Sqrt($upperBound))
[bool[]]$isComposite = New-Object bool[] ($upperBound + 1)
for ([int]$m = 2; $m -le $upperBoundSquareRoot; $m++) {
if (!$isComposite[$m]) {
Write-Host $m" " -NoNewline
for ([int]$k = $m * $m; $k -le $upperBound; $k += $m){
$isComposite[$k] = $true
}
}
}
for ([int]$m = $upperBoundSquareRoot; $m -le $upperBound; $m++){
if (!$isComposite[$m]) {
Write-Host $m" " -NoNewline
}
}
}
runEratosthenesSieve 100
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment