Code Pyre

All Code Dies and Burns in Time

Fork me on GitHub

Project Euler: Problem 5 in PowerShell

| Comments

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

The next problem is just folding two values from an array and replacing them with their LCM, then run again and again until only one item is left in the collection (and you now have the LCM of all entries).

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
function Get-Gcd {
  param($lhs, $rhs)
  if ($lhs -eq $rhs) { return $rhs }
  if ($lhs -gt $rhs) { $a,$b = $lhs,$rhs }
  else { $a,$b = $rhs,$lhs }
  while ($a % $b -ne 0) {
    $tmp = $a % $b
    $a,$b = $b,$tmp
  }
  return $b
}

function Get-Lcm {
  param($lhs, $rhs)
  [long][Math]::Abs($lhs * $rhs) / (Get-Gcd $lhs $rhs)
}

function Get-LcmOfGroup {
  param([int[]]$values)
  $lhs = $values[0]
  $rhs = $values[1]
  $lcm = Get-Lcm $lhs $rhs
  $values = @($lcm) + $values[2..$values.Length]
  if($values.Length -eq 1) { return $lcm }
  else { Get-LcmOfGroup $values }
}

function Solve-Problem5 {
  Get-LcmOfGroup @(1..20)
}

Write-Host "Elapsed Time (s): " (Measure-Command {Solve-Problem5}).TotalSeconds
Write-Host "Solution: " (Solve-Problem5)

Elapsed Time (s):  0.0407472
Solution:  232792560

Comments