Prime numbers will always have a special place in every mathematicians (or cryptographers) heart. The usefulness for the standard PowerShell user is questionable, but just for the fun of it I have created/translated a couple of functions for working with Primes.

The first function is called Get-PrimeNumbers and will, as the name suggests, output the first x number of primes (x being controlled by the Amount parameter). The function is not just looking up numbers in an already prepared list, but are calculating/finding the primes using one of three algorithms; the Standard method as well as the Sieve of Eratosthenes and the Sieve of Sundaram. You can choose between the three by using the Method parameter.

The second function is called Test-IsPrime and can be used to test if a number is a prime or not. This function will return either True of False depending on whether the input is a prime or not. It uses the Rabin-Miller primality test to check for primality.

Add-Type TypeDefinition @"
public enum PrimeMethods
{
Standard,
SieveOfEratosthenes,
SieveOfSundaram
}
"@
function Get-PrimeNumbers {
<#
.SYNOPSIS
Get Prime numbers.
.DESCRIPTION
This function will calculate the prime numbers from 2 to the amount specified using the
Amount parameter. You have a choice of using three different methods to calculate the
prime numbers; the Standard method, the Sieve Of Eratosthenes or the Sieve Of Sundaram.
.EXAMPLE
Get-PrimeNumbers 100
This will list the first 100 prime numbers.
.EXAMPLE
Get-PrimeNumbers 100 -Method 'SieveOfEratosthenes'
This will list the first 100 prime numbers using the Sieve Of Eratosthenes method.
.NOTES
These functions were translated from c# to PowerShell from a post on stackoverflow,
written/collected by David Johnstone, but other authors were responsible for some of them.
Author: Øyvind Kallstad
Date: 09.05.2015
Version: 1.0
.LINK
http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers
http://en.wikipedia.org/wiki/Sieve_of_Sundaram
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Prime_number
#>
[CmdletBinding()]
param (
# The amount of prime numbers to get. The default value is 10.
[Parameter(Position = 0)]
[ValidateRange(1,[int]::MaxValue)]
[int] $Amount = 10,
# The method used to get the prime numbers. Choices are 'Standard', 'SieveOfEratosthenes' and 'SieveOfSundaram'.
# The default value is 'Standard'.
[Parameter()]
[ValidateNotNullOrEmpty()]
[PrimeMethods] $Method = 'Standard'
)
function Get-PrimeNumbersStandardMethod {
param ([int]$Amount)
$primes = New-Object System.Collections.ArrayList
[void]$primes.Add(2)
$nextPrime = 3
while ($primes.Count -lt $Amount) {
$squareRoot = [math]::Sqrt($nextPrime)
$isPrime = $true
for ($i = 0; $primes[$i] -le $squareRoot; $i++) {
if (($nextPrime % $primes[$i]) -eq 0) {
$isPrime = $false
break
}
}
if ($isPrime) {
[void]$primes.Add($nextPrime)
}
$nextPrime += 2
}
Write-Output $primes
}
function Invoke-ApproximateNthPrime {
param ([int]$nn)
[double]$n = $nn
[double]$p = 0
if ($nn -ge 7022) {
$p = $n * [math]::Log($n) + $n * ([math]::Log([math]::Log($n)) 0.9385)
}
elseif ($nn -ge 6) {
$p = $n * [math]::Log($n) + $n * [math]::Log([math]::Log($n))
}
elseif ($nn -gt 0) {
$p = (2,3,5,7,11)[($nn 1)]
}
Write-Output ([int]$p)
}
function Invoke-SieveOfEratosthenes {
param([int]$Limit)
$bits = New-Object TypeName System.Collections.BitArray ArgumentList (($Limit + 1), $true)
$bits[0] = $false
$bits[1] = $false
for ($i = 0; ($i * $i) -le $Limit; $i++) {
if ($bits[$i]) {
for (($j = $i * $i); $j -le $Limit; $j += $i) {
$bits[$j] = $false
}
}
}
Write-Output (,($bits))
}
function Invoke-SieveOfSundaram {
param([int]$Limit)
$limit /= 2
$bits = New-Object TypeName System.Collections.BitArray ArgumentList (($Limit + 1), $true)
for ($i = 1; (3 * ($i + 1)) -lt $Limit; $i++) {
for ($j = 1; ($i + $j + 2 * $i * $j) -le $Limit; $j++) {
$bits[($i + $j + 2 * $i * $j)] = $false
}
}
Write-Output (,($bits))
}
function Get-PrimeNumbersSieveOfEratosthenes {
param([int]$Amount)
$limit = Invoke-ApproximateNthPrime $Amount
[System.Collections.BitArray]$bits = Invoke-SieveOfEratosthenes $limit
$primes = New-Object System.Collections.ArrayList
$found = 0
for ($i = 0; $i -lt $limit -and $found -lt $Amount; $i++) {
if ($bits[$i]) {
[void]$primes.Add($i)
$found++
}
}
Write-Output $primes
}
function Get-PrimeNumbersSieveOfSundaram {
param([int]$Amount)
$limit = Invoke-ApproximateNthPrime $Amount
[System.Collections.BitArray]$bits = Invoke-SieveOfSundaram $limit
$primes = New-Object System.Collections.ArrayList
[void]$primes.Add(2)
$found = 1
for ($i = 1; (2 * ($i + 1)) -le $limit -and $found -lt $Amount; $i++) {
if ($bits[$i]) {
[void]$primes.Add((2 * $i + 1))
$found++
}
}
Write-Output $primes
}
switch ($Method) {
'Standard' {Get-PrimeNumbersStandardMethod $Amount;break}
'SieveOfEratosthenes' {Get-PrimeNumbersSieveOfEratosthenes $Amount;break}
'SieveOfSundaram' {Get-PrimeNumbersSieveOfSundaram $Amount;break}
}
}

view raw
Get-PrimeNumbers.ps1
hosted with ❤ by GitHub

function Test-IsPrime {
<#
.SYNOPSIS
Test if a number is a prime number.
.DESCRIPTION
This function uses the Rabin-Miller primality test to check for primality.
.EXAMPLE
Test-IsPrime 6461335109
Returns True.
.LINK
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
http://rosettacode.org/wiki/Miller-Rabin_primality_test#C.23
.INPUTS
bigint
.NOTES
This code is translated to PowerShell from code found on rosettacode.
Author: Øyvind Kallstad
Date: 11.05.2015
Version: 1.0
#>
[CmdletBinding()]
[OutputType([System.Boolean])]
param (
# The number you want to check for primality.
[Parameter(Position = 0, ValueFromPipeline)]
[bigint]$Number,
# Determines the accuracy of the test. Default value is 40.
[Parameter(Position = 1)]
[ValidateRange(1,[int]::MaxValue)]
[int]$Iterations = 40
)
if ($Number -in 2..3) {
return $true
}
if (($Number -lt 2) -or (($Number % 2) -eq 0)) {
return $false
}
[bigint]$d = $Number 1
[int]$s = 0
while (($d % 2) -eq 0) {
$d /= 2
$s += 1
}
$rng = [System.Security.Cryptography.RandomNumberGenerator]::Create()
[byte[]] $bytes = $Number.ToByteArray().LongLength
[bigint]$a = 0
for ($i = 0; $i -lt $Iterations; $i++) {
do {
$rng.GetBytes($bytes)
$a = [bigint]$bytes
} while (($a -lt 2) -or ($a -ge ($Number 2)))
[bigint]$x = [bigint]::ModPow($a, $d, $Number)
if (($x -eq 1) -or ($x -eq ($Number 1))) {
continue
}
for ($r = 1; $r -lt $s; $r++) {
$x = [bigint]::ModPow($x, 2, $Number)
if ($x -eq 1) {
return $false
}
if ($x -eq ($Number 1)) {
break
}
}
if ($x -ne ($Number 1)) {
return $false
}
}
return $true
}

view raw
Test-IsPrime.ps1
hosted with ❤ by GitHub

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s