バッチファイルでProject Euler（48）

Problem 21

約数の和といえば素因数分解、素因数分解といえばエラトステネスのふるいですが、最初は単純な約数の求め方を使いましょう。例えば、20の約数を求めたいとすると、[√20] = 4だから2〜4までで割り切れるか調べればよいです。forで回す回数が決まっているので処理が速くなります。しかし、その前にルートを求める処理が遅いです。

:sqrt
    setlocal
    set /a r = %1
    :loop_sqrt
        set /a r1 = (%r% + %1 / %r%) / 2
        if %r1% GEQ %r% exit /b %r%
        set /a r = %r1%
        goto :loop_sqrt

何度もgotoを使ってしまっています。なんとかならないでしょうか。
1ずつ大きくなる数を考えればそのルートは変わらないか1大きくなるかのどちらかのはずなので、簡単に求めることができます。

set /a sqrt = 1
for /L %%n in (2, 1, %M%) do (
    set /a _s = !sqrt! + 1
    set /a sq = !_s! * !_s!
    if !sq! LEQ %%n set /a sqrt += 1
    ...

そして真の約数の和を求めます。重複しないように過剰数だった場合だけまたその真の約数の和を求めます。このときルートはこの単純な方法では求められません。上の方法でもいいですが、それより速いのはより近い値を初期値にすることです。元の数のルートで自分を割れば、求める値以上で比較的近い値を得ることができます。
これで2分余りでした。意外と速いですね。

@echo off

call :start_time
setlocal enabledelayedexpansion
set /a N = 10000
set /a M = %N% - 1
set /a s = 0
set /a sqrt = 1
for /L %%n in (2, 1, %M%) do (
    set /a _s = !sqrt! + 1
    set /a sq = !_s! * !_s!
    if !sq! LEQ %%n set /a sqrt += 1
    call :f %%n !sqrt!
    if !ERRORLEVEL! GTR %%n (
        if !ERRORLEVEL! LSS %N% (
            set /a n1 = !ERRORLEVEL!
            set /a s0 = !n1! / !sqrt!
            call :sqrt !n1! !s0!
            call :f !n1! !ERRORLEVEL!
            if !ERRORLEVEL! == %%n (
                set /a s += %%n + !n1!
            )
        )
    )
)
echo %s%
call :check_time
exit /b 0

:f
    setlocal
    set /a s = 1
    for /L %%d in (2, 1, %2) do (
        set /a r = %1 %% %%d
        if !r! == 0 (
            set /a d2 = %1 / %%d
            if %%d == !d2! (
                set /a s += %%d
            ) else (
                set /a s += %%d + !d2!
            )
        )
    )
    exit /b %s%

:sqrt
    setlocal
    set /a r = %2
    :loop_sqrt
        set /a r1 = (%r% + %1 / %r%) / 2
        if %r1% GEQ %r% exit /b %r%
        set /a r = %r1%
        goto :loop_sqrt

:start_time
    call :get_time
    set /a __t0 = %ERRORLEVEL%
    exit /b 0

:check_time
    setlocal
    call :get_time
    set /a t = %ERRORLEVEL% - %__t0%
    if %t% LSS 10 (
        echo 0.0%t%s
    ) else (
        if %t% LSS 100 (
            echo 0.%t%s
        ) else (
            echo %t:~0,-2%.%t:~-2%s
        )
    )
    exit /b 0

:get_time
    setlocal
    set t=%TIME%
    set /a h = %t:~0,2%
    set /a m = 1%t:~3,2% %% 100
    set /a s = 1%t:~6,2% %% 100
    set /a ss = 1%t:~-2% %% 100
    set /a ret = ((%h% * 60 + %m%) * 60 + %s%) * 100 + %ss%
    exit /b %ret%