The smallest number a range of numbers can divide into – using Powershell

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

$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:

 

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.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.