So there I was in work the other day talking maths and an interesting subject came up about calculating the lowest number that a range of numbers can divide into with no remainder. So I decided to try and solve the problem using powershell. There are a number of reasons why, but the main one was that I use it every day.
The problem states that 2520 is the smallest number that the range 1 to 10 can divide into without any remainders – what is the lowest number for the range 1 to 20.
So, at first I tried the brute force approach but found that this was too slow evening going from 1 to 10 – see below
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
$range = 1..10 $startnum = 1 do{ $remainder = $true foreach ($inc in $range) { write-host "the current increment is $inc - the current number is $startnum" -ForegroundColor Yellow if(($startnum % $inc) -ne 0) { $remainder = $false $startnum = $startnum + 1 } } }while($remainder -eq $false) |
Then I looked at the results and saw that prime numbers and prime factors were involved, so took another stab at it and cam up with the below, using 2 functions – isprimenumber and primefactors:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
function primefactors{ Param( [parameter(mandatory=$true)][string]$number) $i = 2 $result = @() do{ if(($number % $i) -ne 0) { $i = $i + 1 } else { $number = $number / $i $result = $result + $i } }while($number -ne 1) return $result } function isprimenumber{ Param( [parameter(mandatory=$true)][string]$number) $result = $false if((primefactors $number).count -eq 1) { $result = $true } return $result } $range = 1..20 $startnum = 1 foreach ($inc in $range) { if(($startnum % $inc) -ne 0) { if(isprimenumber $inc) { $startnum = $startnum * $inc } else { $startnum = $startnum * (primefactors $inc)[0] } } Write-Host "increment = $inc, total = $startnum" -ForegroundColor Yellow } |
As you can see when you run this – its so much faster.