PowerShell Prime

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

Tags: Custom Function, PowerShell

Communary

PowerShell Prime

Leave a Reply Cancel reply

Rate this:

Share this:

Like this:

Related

Leave a Reply Cancel reply