Skip to content

Instantly share code, notes, and snippets.

@shaunhess

shaunhess/Test_Prime_Num_PowerShell

Created October 20, 2013 19:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save shaunhess/7074004 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save shaunhess/7074004 to your computer and use it in GitHub Desktop.
Download ZIP
Testing for Prime Numbers Using Powershell
Raw
Test_Prime_Num_PowerShell
So what is a prime number anyway. Lets see what Wikipedia has to say:
A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2 and 3 in addition to 1 and 6. The fundamental theorem of arithmetic establishes the central role of primes in number theory: any integer greater than 1 can be expressed as a product of primes that is unique up to ordering. This theorem requires excluding 1 as a prime.
Since there are infintely number of primes, it's always fun to see how fast and how many we can find. The largest know prime number has nearly 13 million decimal digits!
Now thats out of the way lets see how we can test to see whether a number is prime or not using Powershell. Today we will look at a few different methods, including my favorite, Sieve of Eratosthenes. The first method we will look at is using a brute force method which is by far the slowest. Now lets look at some code:
function Test-isPrime
{
<#
.Synopsis
Tests if a number is a prime using the brute force method.
.EXAMPLE
Test-isPrime (1..1000)
.EXAMPLE
1..1000 | Test-isPrime
#>
[CmdletBinding()]
Param
(
[Parameter(Mandatory=$true,
ValueFromPipeLine=$true,
ValueFromPipelineByPropertyName=$true,
Position=0)]
[int[]]$number
)
Begin
{
$properties = @{'Number'=$null;'Prime'=$null}
}
Process
{
foreach ($n in $number)
{
$i = 2
$properties.Number = $n
$properties.Prime = $true
if ($n -lt 2)
{
$properties.Prime = $false
}
if ($n -eq 2)
{
$properties.Prime = $true
}
while ($i -lt $n)
{
if ($n % $i -eq 0)
{
$properties.Prime = $false
}
$i++
}
$object = New-Object PSObject –Prop $properties
Write-Output $object
}
}
End
{
}
}
Now lets measure how long it takes to test 1 through 10,000.
PS C:\Windows\system32> Measure-Command {1..10000 | Test-isPrime}
Days : 0
Hours : 0
Minutes : 3
Seconds : 20
Milliseconds : 93
Ticks : 2000930921
TotalDays : 0.00231589226967593
TotalHours : 0.0555814144722222
TotalMinutes : 3.33488486833333
TotalSeconds : 200.0930921
TotalMilliseconds : 200093.0921
This certainly isn't the most efficient way to check whether a number is a prime. So lets spice it up a bit and test if a number is a prime by checking only the numbers between 1 and n/2-1. If we find such a divisor that will be enough to say that n isn't prime:
function Test-isPrime2
{
<#
.Synopsis
Tests if a number is a prime by checking only the numbers between 1 and n/2-1. If
we find such a divisor that will be enough to say that n isn’t prime.
.EXAMPLE
Test-isPrime2 (1..1000)
.EXAMPLE
1..1000 | Test-isPrime2
#>
[CmdletBinding()]
Param
(
[Parameter(Mandatory=$true,
ValueFromPipeLine=$true,
ValueFromPipelineByPropertyName=$true,
Position=0)]
[int[]]$number
)
Begin
{
$properties = @{'Number'=$null;'Prime'=$null}
}
Process
{
foreach ($n in $number)
{
$i = 2
$properties.Number = $n
$properties.Prime = $true
if ($n -lt 2)
{
$properties.Prime = $false
}
if ($n -eq 2)
{
$properties.Prime = $true
}
while ($i -le $n/2)
{
if ($n % $i -eq 0)
{
$properties.Prime = $false
}
$i++
}
$object = New-Object PSObject –Prop $properties
Write-Output $object
}
}
End
{
}
}
Now lets measure how long it takes to test 1 through 10,000.
PS C:\Windows\system32> Measure-Command {1..10000 | Test-isPrime2}
Days : 0
Hours : 0
Minutes : 2
Seconds : 30
Milliseconds : 357
Ticks : 1503579593
TotalDays : 0.00174025415856481
TotalHours : 0.0417660998055556
TotalMinutes : 2.50596598833333
TotalSeconds : 150.3579593
TotalMilliseconds : 150357.9593
Slightly better, but still not very effective for larger numbers. Lets try to improve our code by checking our number against [2, sqrt(n)]. This is correct because if n isn't prime it can be represented as p*q = n. Of course if p > sqrt(n), which we assume can't be true, that will mean that q < sqrt(n).
function Test-isPrime3
{
<#
.Synopsis
Tests if a number is a prime by checking against [2, sqrt(n)]. This is correct,
because if n isn’t prime it can be represented as p*q = n. Of course if
p > sqrt(n), which we assume can’t be true, that will mean that q < sqrt(n).
.EXAMPLE
Test-isPrime3 (1..1000)
.EXAMPLE
1..1000 | Test-isPrime3
#>
[CmdletBinding()]
Param
(
[Parameter(Mandatory=$true,
ValueFromPipeLine=$true,
ValueFromPipelineByPropertyName=$true,
Position=0)]
[int[]]$number
)
Begin
{
$properties = @{'Number'=$null;'Prime'=$null}
}
Process
{
foreach ($n in $number)
{
$i = 2
$sqrtN = [math]::sqrt($n)
$properties.Number = $n
$properties.Prime = $true
if ($n -lt 2)
{
$properties.Prime = $false
}
if ($n -eq 2)
{
$properties.Prime = $true
}
while ($i -le $sqrtN)
{
if ($n % $i -eq 0)
{
$properties.Prime = $false
}
$i++
}
$object = New-Object PSObject –Prop $properties
Write-Output $object
}
}
End
{
}
}
Now lets measure how long it takes to test 1 through 10,000.
PS C:\Windows\system32> Measure-Command {1..10000 | Test-isPrime3}
Days : 0
Hours : 0
Minutes : 0
Seconds : 6
Milliseconds : 32
Ticks : 60323509
TotalDays : 6.98188761574074E-05
TotalHours : 0.00167565302777778
TotalMinutes : 0.100539181666667
TotalSeconds : 6.0323509
TotalMilliseconds : 6032.3509
As you can see this is a dramatic increase in performance, but we can still do better. Time to implement the Sieve of Eratosthenes.
function Test-isPrime4
{
<#
.Synopsis
Tests if a number is a prime by using the Eratosthenes sieve.
.EXAMPLE
Test-isPrime4 -max 10
#>
Param
(
[Parameter(Mandatory=$true,
ValueFromPipeLine=$true,
ValueFromPipelineByPropertyName=$true,
Position=0)]
[int]$maxnumber
)
Begin
{
$sieve = New-Object 'System.Collections.Generic.SortedDictionary[int, bool]'
for ($i=2;$i -lt $maxnumber+1; $i++)
{
<#Intially set all numbers in the list to true. We will use
Eratosthenes sieve to find which integers are not prime.#>
$sieve[$i] = $true
}
}
Process
{
foreach ($i in @($sieve.GetEnumerator()))
{
<#Starting from p, count up in increments of p and mark each of these
numbers greater than p itself in the list. These numbers will be 2p, 3p,
4p, etc.; note that some of them may have already been marked.
Initially, let p equal 2, the first prime number #>
$p = 2
while (($i.Key * $p) -le $maxnumber)
{
if ($sieve.ContainsKey($i.Key * $p))
{
$sieve[($i.Key * $p)] = $false
}
$p++
}
}
Write-Output $sieve
}
End
{
}
}
Now lets measure how long it takes to test 1 through 10,000.
PS C:\Windows\system32> Measure-Command {Test-isPrime4 -maxnumber 10000}
Days : 0
Hours : 0
Minutes : 0
Seconds : 2
Milliseconds : 979
Ticks : 29797250
TotalDays : 3.44875578703704E-05
TotalHours : 0.000827701388888889
TotalMinutes : 0.0496620833333333
TotalSeconds : 2.979725
TotalMilliseconds : 2979.725
Implementing the right algortihm, with relatively minor changes to our function, can have substantial benefits. Even if it is an ancient algorithm!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment