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

Problem 21

大きな配列を取ると劇的に遅くなるので、小さい配列でエラトステネスのふるい的に約数の和を取ってみました。ただし、そうすると約数の和のためにもう一つ配列が必要になります。例えば、10なら、a[10]=10とb[10]=1とします。bが約数の和です。2で割り切れるから、a[10]=10/2=5、b[10]=1*(1+2)=3、5が残っているので、b[10]=3*(1+5)=18。真の約数の和は8となります。そして、過剰数だったら最初にやった2から割っていく方法を使います。その際のsqrtは前回の方法を使います。
最初の方法より少し速くなりました。やはりsqrtがネックのようです。

@echo off

setlocal enabledelayedexpansion
set /a N = 10000
call :num_sqrt_iteration %N%
set /a num_iter = %ERRORLEVEL% + 1
set /a N_1 = %N% + 1
call :sqrt %N%
set /a M = %ERRORLEVEL%

rem // calculate prime numbers
set /a ps.size = 1
set /a ps_0 = 2
for /L %%k in (3, 2, %M%) do (
    call :is_prime %%k
    if !ERRORLEVEL! == 1 call :push_vector ps %%k
)

rem // calculate sum of divisors
set /a s = 0
for /L %%b in (2, %M%, %N_1%) do (
    set /a e = %%b + %M%
    call :sieve a b %%b !e!
    set /a e_1 = !e! - 1
    for /L %%n in (%%b, 1, !e_1!) do (
        set /a k = %%n - %%b
        set /a sd = "b_!k!" - %%n
        if !sd! GTR %%n (
            call :sum_divs !sd!
            if %%n == !ERRORLEVEL! set /a s += !sd! + %%n
        )
    )
)
echo %s%
exit /b 0

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

:sqrt
    setlocal
    set /a r = %1
    for /L %%k in (1, 1, %num_iter%) do (
        set /a r1 = !r! + %1 / !r!
        set /a r1 /= 2
        if !r1! GEQ !r! exit /b !r!
        set /a r = !r1!
    )

:is_prime
    set /a max_index = "ps.size" - 1
    for /L %%k in (0, 1, %max_index%) do (
        set /a r = %1 %% "ps_%%k"
        if !r! == 0 exit /b 0
    )
    exit /b 1

:sieve
    set /a _e = %4 - 1
    call :range %1 %3 %4
    call :fill %2 %M% 1
    set /a k = 0
    set /a p = 2
    :loop_sieve
        set /a _b = (%3 + %p% - 1) / %p% * %p%
        if %_b% == %p% set /a _b += %p%
        for /L %%k in (%_b%, %p%, %_e%) do (
            set /a i = %%k - %3
            set /a a_!i! /= %p%
            set /a _s = 1 + %p%
            set /a r = "a_!i!" %% %p%
            if !r! == 0 call :div_exp
            set /a b_!i! *= !_s!
        )
        set /a k += 1
        set /a p = "ps_%k%"
        if %p% GTR 0 (
            set /a p_sq = %p% * %p%
            if !p_sq! LSS %4 goto :loop_sieve
        )
    
    set /a M_1 = %M% - 1
    for /L %%k in (0, 1, %M_1%) do (
        set /a ak = "%1_%%k"
        if !ak! GTR 1 set /a %2_%%k *= !ak! + 1
    )
    exit /b 0

:div_exp
    :loop_div_exp
        set /a a_!i! /= %p%
        set /a _s = !_s! * %p% + 1
        set /a r = a_!i! %% %p%
        if %r% NEQ 0 exit /b 0
        goto :loop_div_exp

:sum_divs
    setlocal
    set /a s = 1
    call :sqrt %1
    set /a max = %ERRORLEVEL%
    for /L %%d in (2, 1, %max%) do (
        set /a r = %1 %% %%d
        if !r! == 0 (
            set /a s += %%d
            set /a q = %1 / %%d
            if %%d NEQ !q! set /a s += !q!
        )
    )
    exit /b %s%

:range
    if "%3" == "" call :range %1 0 %2 1 & exit /b 0
    if "%4" == "" call :range %1 %2 %3 1 & exit /b 0
    
    set /a max_index = (%3 - %2) / %4 - 1
    set /a %1.size = %max_index% + 1
    for /L %%i in (0, 1, %max_index%) do (
        set /a %1_%%i = %2 + %%i * %4
    )
    exit /b 0

:fill
    set /a %1.size = %2
    set /a max_index = %2 - 1
    for /L %%k in (0, 1, %max_index%) do set /a %1_%%k = %3
    exit /b 0

:push_vector
    set /a size = "%1.size"
    set /a %1_%size% = %2
    set /a %1.size += 1
    exit /b 0