PowerShell で Project Euler 5

問題

• 本家：Problem 5 - Project Euler
• 翻訳：Problem 5 - PukiWiki

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

ユークリッドの互除法を使って

20 |
    ? {$_ -ge 1} |
    % {1..$_} |
    % {$acc = 1} {
        $min, $max = if ($_ -lt $acc) {$_, $acc} else {$acc, $_}
        while ($min -gt 0) {$min, $max = ($max % $min), $min}
        $acc = $acc * $_ / $max
    } {$acc}

$f(n) $$= \text{lcm}(1 \dots n) $$= \text{lcm}(\text{lcm}(1 \dots n -1), n) $$= \text{lcm}(f(n -1), n) $$= \frac{n}{\gcd(f(n -1), n)} f(n -1)$

• f(n) : 1からnまでの整数の最小公倍数
• lcm : 最小公倍数
• gcd : 最大公約数

エラトステネスの篩を使って

20 |
    ? {$_ -ge 2} |
    % {
        $n = $_
        $skip = New-Object System.Collections.BitArray ($_ - 1)
        2..$_
    } |
    ? {-not $skip.Get($_ - 2)} |
    % {$acc = 1} {
        for($i = $_ * $_; $i -le $n; $i += $_)
            {$skip.Set($i - 2, $true)}

        for($i = $_; $i -le $n; $i *= $_)
            {$acc *= $_}
    } {$acc}

f(n) = \prod_{p;\text{prime}} p^{\max(0, \lfloor \log_p n \rfloor)}

おわり

ユークリッドの互除法の速さたるや。ちなみに次が成り立つ。

\frac{n}{\gcd(f(n -1), n)} = \left\{
\begin{array}{ll}
p & (n = p^k;~ p \text{は素数}; ~ k \text{は正整数}) \\
1 & (\text{otherwise})
\end{array}
\right.