A bit off the wall… Here’s a script that started life in 1980 in a magazine article and which I’ve revisited over the years, converting to new languages as they’ve come along. Here’s the latest PowerShell version, updated since I first created it in 2006.

Sample:

PS:\> get-factors 21

21 = 3 x 7

PS:\> get-factors 21 -Verbose

VERBOSE: Finding factors of 21 (with root ~4.58)

VERBOSE: Trying 2

VERBOSE: 2 is not a factor

VERBOSE: Adding 1; divisor is now 3

VERBOSE: Trying 3

VERBOSE: Found factor 3

VERBOSE: Remainder is now 7 (root ~2.65), finding factors of this…

VERBOSE: Trying 3

VERBOSE: 3 is not a factor

VERBOSE: Adding 2; divisor is now 5

VERBOSE: Trying 5

VERBOSE: 5 is not a factor

VERBOSE: Adding 2; divisor is now 7

VERBOSE: Trying 7

VERBOSE: Found factor 7

VERBOSE: Remainder is 1, all factors found

21 = 3 x 7

See comments in the code for further info…

# Calculates Prime Factors of Given Integer # # Algorithm based on an article from "Practical Computing", February 1980 (when computer magazines were really about computing:-) # # This is a standard sieve, but rather than trying all increasing integers as divisors the next possible divisor is # calculated by adding an increment from a (repeating) sequence - thereby missing any even numbers or any multiples of 3 or 5. # # The initial divisor is 2. The increment list repeats from the forth entry, so the possible divisors will start with: # # Divisor: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97 # Increment: +1 +2 +2 +4 +2 +4 +2 +4 +6 +2 +6 [repeat] +4 +2 +4 +2 +4 +6 +2 +6 [repeat] +4 +2 +4 +2 +4 +6 +2 +6 # # This approach skips a large number of trial division operations at the expense of some array (list) management. # # PowerShell version, Chris Warwick, 2006 # Last modified September 2012 # . [CmdletBinding()] Param ($n=$(Throw "Specify a number to factorise")) $DivisorIncrements=1,2,2,4,2,4,2,4,6,2,6 $IncrementLength=$DivisorIncrements.Length $Root=[Math]::Pow($n,0.5) # All factors found once divisor is greater than number's square-root $Divisor=2 # Initial divisor - try this as first factor $Number=$n # Save original number $Answer="" # Resultant list of factors appended to this string $i=0 # Index into increment list Write-Verbose ("Finding factors of $n (with root ~{0:0.##})" -f $Root) For (;;) { Write-Verbose "Trying $Divisor" $Remainder=$n/$Divisor If ($Remainder -eq [Math]::Truncate($Remainder)) { # Remainder is a whole number, found a factor... Write-Verbose "Found factor $Divisor" If ($Remainder -eq 1) { # All factors have been found Write-Verbose "Remainder is 1, all factors found" Break } $n=$Remainder # ...remove this factor and calculate factors of remainder $Root=[Math]::Pow($n,0.5) # ...new end-point Write-Verbose ("Remainder is now $Remainder (root ~{0:0.##}), finding factors of this..." -f $Root) $Answer+=" $Divisor x" # ... save list of factors for display } Else { # Current divisor was not a factor Write-Verbose "$Divisor is not a factor" $Divisor+=$DivisorIncrements[$i] # Add to the divisor, skipping multiples of 2, 3, 4, 5 Write-Verbose "Adding $($DivisorIncrements[$i]); divisor is now $Divisor" $i++ # Next time add the next increment from the list If ($i -ge $IncrementLength) { # Got to end of increments list... $i=3 # List repeats from the 4th element If ($Divisor -gt $Root) { # Check at this point that the divisor isn't too large Write-Verbose "Divisor now greater than Sqrt of remainder... done" Break } } } } If ($n -eq $Number) {"$n is Prime"} Else { "$Number =$Answer $n" # Append last remainder and display list of factors }