Monday, December 29, 2008

Project Euler and PowerShell - Problem 5

Moving on...

Problem 5: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest number that is divisible with no remainder evenly divisible by all of the numbers from 1 to 20?
function modFunction ($mod)
{
$number = 1
$start = $mod
do {
if($number%$mod -eq 0)
{
$mod--
}
else
{
$number++;
$mod=$start
}
}
until ($mod -eq 1)
$number
}

modFunction 20
While short, this is clearly a brute force approach. Anyone have a more efficient algorithm?

1 comment:

Mike Foster said...

Still a brute force approach, but I found this code to be substantially faster. Since the end result has to be a multiple of 20, I've started at 20 and incremented by 20 each time. I also found having multiple conditions in the loop to be faster than iterating through potential factors individually.

$X=20

do{
$X=$X+20
}
while (($X%2 -ne 0) -or ($X%3 -ne 0) -or ($X%4 -ne 0) -or ($X%5 -ne 0) -or ($X%6 -ne 0) -or ($X%7 -ne 0) -or ($X%8 -ne 0) -or ($X%9 -ne 0) -or ($X%11 -ne 0) -or ($X%12 -ne 0) -or ($X%13 -ne 0) -or ($X%14 -ne 0) -or ($X%15 -ne 0) -or ($X%16 -ne 0) -or ($X%17 -ne 0) -or ($X%18 -ne 0) -or ($X%19 -ne 0) -or ($X%20 -ne 0))

$X