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

Problem 7

配列もどきを使うにしても、大きな配列は使えないことがわかりました。
そこでエラトステネスのふるいを小さな範囲で行い、それを繰り返すようにします。それ以前に必要な範囲の素数はこれまたエラトステネスのふるいよって求めておきます。これで、4分あまりで答えが出るようになりました。

@echo off

setlocal
set /a N = 10001
call :get_time
set /a t0 = %ERRORLEVEL%
call :log2 %N%
set /a M = %N% * %ERRORLEVEL%
call :sqrt %M%
set /a L = %ERRORLEVEL%
call :make_primes ps %L%
call :get_time
call :solve
echo %ERRORLEVEL%
call :get_time
set /a t = %ERRORLEVEL% - %t0%
echo %t:~0,-2%.%t:~-2%s
exit /b 0

:sqrt
    setlocal
    set /a n = %1
    set /a m = %1
    :loop_sqrt
        set /a m1 = (%m% + %n% / %m%) / 2
        if %m1% GEQ %m% exit /b %m%
        set /a m = %m1%
        goto :loop_sqrt

:make_primes
    set /a aa.size = %2 + 1
    call :fill_vector aa 1
    set /a k = 2
    :loop_make_primes
        set /a b = "aa_%k%"
        if %b% == 0 set /a k += 1 & goto :loop_make_primes
        set /a k2 = %k% * 2
        for /L %%i in (%k2%, %k%, %2) do set /a aa_%%i = 0
        set /a k += 1
        set /a k_sq = %k% * %k%
        if %k_sq% LEQ %2 goto :loop_make_primes
    
    set /a k = 3
    :loop_make_primes2
        set /a b = "aa_%k%"
        if %b% == 1 call :push_vector %1 %k%
        set /a k += 1
        if %k% LSS %2 goto :loop_make_primes2
    exit /b 0

:sieve
    call :fill_vector %1 1
    call :sqrt %3
    set /a p_limit = %ERRORLEVEL%
    set /a k = 0
    :loop_sieve
        set /a p = "ps_%k%"
        set /a m0 = ((%2 + %p% - 1) / (%p% * 2) * (%p% * 2) + %p% - %2) / 2
        set /a L_1 = %L% - 1
        for /L %%m in (%m0%, %p%, %L_1%) do set /a %1_%%m = 0
        set /a k += 1
        if %k% == %ps.size% exit /b 0
        if %p% LSS %p_limit% goto :loop_sieve
    exit /b 0

:solve
    set /a counter = 1 + %ps.size%
    set /a begin = %L% + 1
    set /a L_2 = %L% / 2
    :loop_solve
        set /a end = %begin% + %L%
        call :sieve aa %begin% %end%
        set /a k = 0
        :loop_solve2
            set /a b = "aa_%k%"
            if %b% == 1 set /a counter += 1
            set /a p = %begin% + %k% * 2
            if %counter% == %N% exit /b %p%
            set /a k += 1
            if %k% LSS %L_2% goto :loop_solve2
        set /a begin += %L%
        goto :loop_solve

:log2
    setlocal
    if %1 == 1 exit /b 0
    set /a n = "%1 >> 1"
    call :log2 %n%
    set /a m = %ERRORLEVEL% + 1
    exit /b %m%

:fill_vector
    set /a max_index = "%1.size" - 1
    for /L %%i in (0, 1, %max_index%) do set /a %1_%%i = %2
    exit /b 0

:print_vector
    setlocal
    set vector=%1
    set /a size = "%vector%.size"
    if %size% == 0 echo %2 & exit /b 0
    set /a e = "%vector%_0"
    set s=%e%
    set /a k = 1
    :loop_print_vector
        if %k% == %size% echo %s% & exit /b 0
        set /a e = "%vector%_%k%"
        set s=%s% %e%
        set /a k += 1
        goto :loop_print_vector

:push_vector
    set /a size = "%1.size"
    set /a %1_%size% = %2
    set /a %1.size = %size% + 1
    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%